Segment Tree с Lazy Propagation
Обычное дерево отрезков умеет:
Но если нужно прибавить число ко всему отрезку , то делать это поэлементно — дорого. Lazy propagation позволяет делать обновления отрезка и запросы отрезка за .
Есть массив . Нужно поддерживать операции:
add(l, r, y): прибавить ко всем элементам sum(l, r): найти сумму на отрезке Каждый узел дерева хранит:
t[x] — ответ для всего отрезка узла (в нашем случае сумма)lz[x] — “ленивое значение”: сколько надо прибавить ко всем элементам отрезка узла,
но мы пока не спускали это обновление в детейТо есть lz[x] — это отложенное обновление.
apply(x, l, r, y)Применить прибавление к всем индексам на отрезкке узла x = [l..r]:
lz[x] добавим $y` (помним, что дети тоже должны получить это позже)push(x, l, r)Если у узла есть отложенное lz[x], нужно перед спуском ниже протолкнуть его детям:
apply к левому и правому сынуlz[x]Важно: push вызывается перед тем, как мы идём рекурсией в детей.
pull(x)После обновления детей нужно пересчитать текущий узел:
t[x] = t[2x] + t[2x+1] (для суммы)upd(...)Если текущий узел полностью совпадает с запросом :
apply(...) и выходим (не лезем глубже)Иначе:
push(...)pull(...)get(...)Если текущий узел полностью совпадает с запросом:
t[x]Иначе:
push(...) (чтобы дети имели актуальные значения)#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;
}