Дарахти сегментӣ бо паҳнкунии танбалона
Дарахти оддии сегментҳо метавонад:
Аммо агар лозим бошад ба тамоми порча ададро илова кунем, пас инро ба таври унсур-ба-унсур кардан — гарон аст. 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;
}