Дарахти порчаҳо
Дарахти сегментҳо (Segment Tree) — сохтори додаҳо барои ҷавоби зуд ба дархостҳо дар зерқисми массив ва навсозии элементҳо.
Одатан барои дархостҳои навъи зерин истифода мешавад:
Массиви ҳаст.
Мо дарахти бинарӣ месозем, ки дар он:
Барои сумма:
Рекурсивӣ:
Мураккабӣ:
Навсозӣ :
Мураккабӣ:
Ёфтани сумма дар :
Мураккабӣ: (ба ҳисоби миёна/одатан), баҳодиҳии болоӣ барои sum-segtree-и стандартӣ
Одатан дарахтро дар массиви андозааш тақрибан нигоҳ медоранд:
#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;
}