Сегодня разбираем Дерево Отрезков на указателях.
Идея
Идея дерева отрезков заключается в том, чтобы разбить весь массив на непересекающиеся отрезки, организованные в виде двоичного дерева. Каждый узел этого дерева хранит информацию о своём отрезке - в нашем случае это сумма элементов на этом отрезке. Особенностью реализации на указателях является то, что узлы создаются динамически в процессе построения и хранят ссылки на своих детей в виде указателей.
Разберем задачку
Есть массив чисел. Хотим уметь делать две операции быстро:
1. Прибавить число к одному элементу (a[k] += x)
2. Посчитать сумму на любом отрезке массива (sum(l, r))
Наивное решение (просто хранить массив) даёт O(n), а ДО - O(log n)
Код
struct Segtree {
int l, r, sum = 0;
Segtree *left = 0, *right = 0;
Segtree(int l, int r) : l(l), r(r) {
if (l + 1 < r) {
int m = (l + r) / 2;
left = new Segtree(l, m);
right = new Segtree(m, r);
}
}
void add(int k, int x) {
sum += x;
if (left) {
if (k < left->r) left->add(k, x);
else right->add(k, x);
}
}
int get_sum(int ql, int qr) {
if (ql <= l && r <= qr) return sum;
if (qr <= l || r <= ql) return 0;
return left->get_sum(ql, qr) + right->get_sum(ql, qr);
}
};Использование:
Node tree(0, n); // n — размер массива
tree.add(3, 5); // a[3] += 5
cout << tree.get_sum(1, 7); // сумма от 1 до 6
Условия
Наша функция должна быть ассоциативной (код выше делаем складывание), т.е. чтоб можно переставлять скобки/числа без изменения результата.
@postupashki_prog