Segment Tree with Lazy Propagation
A regular segment tree can:
But if you need to add a number to the whole segment , doing it element by element is expensive. Lazy propagation allows doing range updates and range queries in .
There is an array . You need to support operations:
add(l, r, y): add to all elements sum(l, r): find the sum on the segment Each tree node stores:
t[x] — the answer for the whole segment of the node (in our case sum)lz[x] — a “lazy value”: how much needs to be added to all elements of the node’s segment,
but we have not pushed down this update to the children yetThat is, lz[x] is a deferred update.
apply(x, l, r, y)Apply adding to all indices on the segment of node x = [l..r]:
tolz[x]` (remember that the children must also receive this later)push(x, l, r)If a node has a deferred lz[x], before going down we need to push it to its children:
apply to the left and right childlz[x]Important: push is called before we go recursively into the children.
pull(x)After updating the children, we need to recompute the current node:
t[x] = t[2x] + t[2x+1] (for sum)upd(...)If the current node fully matches the query :
apply(...) and exit (don’t go deeper)Otherwise:
push(...)pull(...)get(...)If the current node fully matches the query:
t[x]Otherwise:
push(...) (so that the children have up-to-date values)#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define fi first
#define se second
const int N = 200100;
const int mod = 998244353;
using namespace std;
int n;
int a[N];
long long t[4 * N];
long long lz[4 * N];
long long comb(long long x, long long y) {
return x + y;
}
void pull(int x) {
t[x] = comb(t[x * 2], t[x * 2 + 1]);
}
void apply(int x, int l, int r, int y) {
t[x] += 1ll * y * (r - l + 1);
lz[x] += y;
}
void push(int x, int l, int r) {
if (lz[x] == 0) {
return;
}
int m = (l + r) / 2;
apply(x * 2, l, m, lz[x]);
apply(x * 2 + 1, m + 1, r, lz[x]);
lz[x] = 0;
}
void build(int x, int l, int r) {
if (l == r) {
t[x] = a[l];
return;
}
int m = (l + r) / 2;
build(x * 2, l, m);
build(x * 2 + 1, m + 1, r);
pull(x);
}
void upd(int x, int l, int r, int tl, int tr, int y) {
if (tl > tr) {
return;
} else if (l == tl && r == tr) {
apply(x, l, r, y);
return;
}
push(x, l, r);
int m = (l + r) / 2;
upd(x * 2, l, m, tl, min(m, tr), y);
upd(x * 2 + 1, m + 1, r, max(m + 1, tl), tr, y);
pull(x);
}
int get(int x, int l, int r, int tl, int tr) {
if (tl > tr) {
return 0;
} else if (l == tl && r == tr) {
return t[x];
}
push(x, l, r);
int m = (l + r) / 2;
return comb(get(x * 2, l, m, tl, min(m, tr)), get(x * 2 + 1, m + 1, r, max(m + 1, tl), tr));
}
int main() {
ios_base::sync_with_stdio(0);
n = 3;
a[1] = 1;
a[2] = 3;
a[3] = 1;
build(1, 1, n);
upd(1, 1, n, 2, 3, 3);
cout << get(1, 1, n, 1, 3) << endl;
return 0;
}