Oraliqlar daraxtida erinchoq yangilashlar
Oddiy oraliqlar daraxti quyidagilarni qila oladi:
Lekin agar butun oraliqga son qo‘shish kerak bo‘lsa, buni elementma-element qilish — qimmat. Lazy propagation oraliq yangilashlari va oraliq so‘rovlarini da bajarishga imkon beradi.
massivi bor. Quyidagi amallarni qo‘llab-quvvatlash kerak:
add(l, r, y): dagi barcha elementlarga qo‘shishsum(l, r): oraliqdagi summani topishDaraxtning har bir tuguni quyidagilarni saqlaydi:
t[x] — tugun oraliqsi uchun butun javob (bizning holatda summa)lz[x] — “dangasa qiymat”: tugun oraliqsidagi barcha elementlarga qancha qo‘shish kerak,
lekin biz hali bu yangilashni bolalarga tushirmaganmizYa’ni lz[x] — bu kechiktirilgan yangilash.
apply(x, l, r, y)x = [l..r] tugun oraliqsidagi barcha indekslarga qo‘shishni qo‘llash:
lz[x] ga $y` qo‘shamiz (bolalar ham buni keyinroq olishi kerakligini eslaymiz)push(x, l, r)Agar tugunda kechiktirilgan lz[x] bo‘lsa, pastga tushishdan oldin uni bolalarga itarmoq kerak:
apply ni qo‘llaymizlz[x] ni nolga tushiramizMuhim: push biz rekursiya bilan bolalarga ketishimizdan oldin chaqiriladi.
pull(x)Bolalarni yangilagandan so‘ng joriy tugunni qayta hisoblash kerak:
t[x] = t[2x] + t[2x+1] (summa uchun)upd(...)Agar joriy tugun so‘rov bilan to‘liq mos kelsa:
apply(...) qilamiz va chiqamiz (chuqurroq kirmaymiz)Aks holda:
push(...) qilamizpull(...)get(...)Agar joriy tugun so‘rov bilan to‘liq mos kelsa:
t[x] ni qaytaramizAks holda:
push(...) qilamiz (bolalarda qiymatlar aktual bo‘lishi uchun)#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;
}