Дерево отрезков
Дерево отрезков (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;
}