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