Oralilar daraxti
Oralilar daraxti (Segment Tree) — massivning kichik oraliqsi bo‘yicha so‘rovlarga tez javob berish va elementlarni yangilash uchun ma’lumotlar tuzilmasi.
Odatda quyidagi turdagi so‘rovlar uchun ishlatiladi:
massivi bor.
Biz ikkilik daraxt quramiz, bunda:
Yig‘indi uchun:
Rekursiv:
Murakkablik:
ni yangilash:
Murakkablik:
da yig‘indini topish:
Murakkablik: (o‘rtacha/odatda), standart sum-segtree uchun yuqori baho
Odatda daraxtni taxminan o‘lchamli massivda saqlashadi:
#include <bits/stdc++.h>
using namespace std;
const int N = 100100;
int n;
int a[N];
long long t[4 * N];
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);
t[x] = t[x * 2] + t[x * 2 + 1];
}
void upd(int x, int l, int r, int i, int y) {
if (l == r) {
t[x] = y;
return;
}
int m = (l + r) / 2;
if (i <= m) {
upd(x * 2, l, m, i, y);
} else {
upd(x * 2 + 1, m + 1, r, i, y);
}
t[x] = t[x * 2] + t[x * 2 + 1];
}
long long 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];
}
int m = (l + r) / 2;
return get(x * 2, l, m, tl, min(m, tr)) + get(x * 2 + 1, m + 1, r, max(m + 1, tl), tr);
}
int main() {
n = 5;
a[1] = 1;
a[2] = 1;
a[3] = 4;
a[4] = 2;
a[5] = 3;
build(1, 1, n);
upd(1, 1, n, 2, 10);
cout << get(1, 1, n, 1, 4) << "\n";
return 0;
}