Hello guys, after learning Segment Tree, I approach to learn segment tree with LAZY PROPAGATION I tried to implemented it by do this task increase V to all elements in range a to b and get sum of elements in this range
. This is my code:
#include <bits/stdc++.h>
using namespace std;
struct Node {
int val;
int lazy;
};
struct Segment {
int n;
Node nodes[400001];
Segment (int n) {
this->n = n;
for (int i = 0; i <= 4*n; i++)
nodes[i] = {0, 0};
}
void down(int id) {
int t = nodes[id].lazy;
nodes[id << 1].val += t;
nodes[id << 1].lazy += t;
nodes[id << 1 | 1].val += t;
nodes[id << 1 | 1].lazy += t;
nodes[id].lazy = 0;
}
void update(int id, int l, int r, int u, int v, int val) {
if (l > v || r < u)
return;
if (u <= l && r <= v) {
nodes[id].val += val;
nodes[id].lazy += val;
return;
}
down(id);
int m = (l + r) >> 1;
update(id << 1, l, m, u, v, val);
update(id << 1 | 1, m + 1, r, u, v, val);
nodes[id].val = nodes[id << 1].val + nodes[id << 1 | 1].val;
}
int get(int id, int l, int r, int u, int v) {
if (l > v || r < u) {
return 0;
}
if (u <= l && r <= v)
return nodes[id].val;
down(id);
int m = (l + r) >> 1;
return get(id << 1, l, m, u, v) + get(id << 1 | 1, m + 1, r, u, v);
}
};
int main() {
Segment seg(10);
seg.update(1, 1, 10, 1, 5, 10);
cout << seg.get(1, 1, 10, 1, 5) << endl;
}
And the answer after running is 10
(but correct answer is 50
). Did I implement wrongly?
Thanks so much, guys :D
Have you tried the following:
98% of WAs and REs can be resolved this way. People here don't have the time to delve into every code posted here, it's much harder to debug somebody else's code and being able to debug your own code is a valuable skill. It is also a very routine process that can be learned much faster than problem solving and algorithms.
Line 36 should be
nodes[id].val += (r - l + 1) * val;
There might be some other mistakes as well, didn't see the code carefully.