Дерево отрезков
Содержание
Задача
Нам дан массив $a_0,\ a_1,\ \ldots,\ a_{n - 1}$. Требуется обрабатывать два типа запросов:
- Присвоить $a_x$ значение $k$ ($a_x\ :=\ k$).
- Узнать сумму элементов $a_l,\ a_{l + 1},\ \ldots,\ a_{r}$.
Мы хотим, чтобы каждый запрос обрабатывался за $O(\log n)$.
Замечание. Если запросов обновления нет, то данная задача решается с помощью префиксных сумм.
Идея
Нам понадобится хранить сумму на некоторых подотрезках, а потом склеивать их при ответе на запрос. Сделаем с исходным массивом следующие манипуляции:
- Посчитаем сумму всего массива и где-нибудь запишем.
- Разделим его пополам, посчитаем сумму на половинах и тоже где-нибудь запишем.
- Каждую половину потом разделим пополам ещё раз, и так далее, пока не придём к отрезкам длины 1.
Пусть мы проделали такую операцию. Тогда мы можем представить наши вычисления в виде дерева с соответствующей структурой: <img src="http://i.imgur.com/GGBmcEP.png">
Такое дерево имеет высоту $O(\log n)$, при этом каждая его вершина хранит сумму на каком-то подотрезке массива. Ровно эту структуру данных мы и будем называть деревом отрезков.
Утверждение:
Вершин в дереве $O(n)$
Доказательство:
Если разбить дерево на "слои", то в них будет $$1\ +\ 2\ +\ 4\ +\ \ldots\ + 2^{h-1}$$ вершин суммарно (если мы обозначили высоту дерева за $h$), что равно $O(2^h)$. При $h\ =\ O(\log n):\ O(2^h)\ =\ O(n)$.
Построение
Мы еще не сказали, как быстро посчитать значения сумм для всех вершин. Строить будем такой рекурсивной процедурой:
- Смотрим на текущие параметры $[l,\ r)$ вершины (иначе говоря, границы ее отрезка).
- Если $r\ -\ l\ =\ 1$, то вершина отвечает ровно за 1 элемент, и сумма считается тривиально.
- Иначе мы разбиваем отрезок на два: $m\ := \lfloor\frac{l + r}{2}\rfloor;\ [l,\ r)\ \rightarrow\ [l,\ m),\ [m,\ r)$. Выполним процедуру рекурсивно для новых отрезков (назвав новые две вершины детьми текущей, а потом сохраним $sum_{[l,\ r)}\ =\ sum_{[l,\ m)}\ +\ sum_{[m,\ r)}$ в своей вершине.
Сохранять все вершины будем в массив, поддерживая такую нумерацию:
- Если вершина --- корень, то у нее номер 1.
- Если у вершины с номером $v$ есть левый и правый ребенок, то их номера — $2 \cdot v$ и $2 \cdot v + 1$.
Запрос суммы
Проведем следующую операцию:
- Запомним параметры $[l_q,\ r_q)$ запроса.
- Посмотрим на текущую вершину (изначально — корень дерева). Если ее отрезок не пересекается с отрезком запроса, то все вершины в ее поддереве нам тоже неинтересны, поэтому можно не рассматривать эту вершину.
- Если отрезок нашей вершины вложен в отрезок запроса, то мы можем прибавить посчитанное в вершине значение суммы к ответу.
- Если отрезок нашей вершины пересекается с отрезком запроса, то рекурсивно проведем операцию в наших потомках.
Очевидно, что таким образом мы действительно посчитаем сумму на всем отрезке.
Утверждение:
Данная процедура работает за $O(\log n)$
Доказательство:
Посмотрим на самую левую и самую правую вершины, посчитанные при ответе на запрос. Все вершины, лежащие между ними, были рассмотрены за $O(1)$, потому что лежали внутри запроса. Аналогично за $O(1)$ была рассмотрена каждая вершина вне отрезка. За время спуска к двум крайним вершинам процедура рассмотрела $O(\log n)$ вершин, которые были обработаны за $O(1)$.
Запрос обновления элемента
Для обновления одного элемента надо спуститься к нему по дереву, изменить значение в листе, а потом заново пересчитать все значения в вершинах на пути до корня. Аналогично, это работает за $O(\log n)$.
1 int t[MAXN * 4];
2 int a[MAXN];
3
4 void build(int v, int l, int r) {
5 if (l + 1 == r) {
6 t[v] = a[l];
7 return;
8 }
9 int m = (l + r) / 2;
10 build(2 * v, l, m);
11 build(2 * v + 1, m, r);
12 t[v] = t[2 * v] + t[2 * v + 1];
13 }
14
15 void upd(int v, int l, int r, int pos, int x) {
16 if (l + 1 == r) {
17 t[v] = x;
18 return;
19 }
20 int m = (l + r) / 2;
21 if (pos < m) {
22 upd(2 * v, l, m, pos, x);
23 }
24 else {
25 upd(2 * v + 1, m, r, pos, x);
26 }
27 t[v] = t[2 * v] + t[2 * v + 1];
28 }
29
30 int get(int v, int l, int r, int ql, int qr) {
31 if (ql >= r || l >= qr) {
32 return NEUTRAL;
33 }
34 if (ql <= l && qr <= r) {
35 return t[v];
36 }
37 int m = (l + r) / 2;
38 return get(2 * v, l, m, ql, qr) + get(2 * v + 1, m, r, ql, qr));
39 }
Массовые операции
Мы уже решили исходную задачу, поэтому давайте просто дополним статью еще несколькими трюками. Если в задаче нам требуется делать какую-то операцию на отрезке (например, присвоить всем элементам значение $x$), то мы будем находить соответствующие запросу изменения вершины, и в них пользоваться техникой отложенных операций.
Также может быть интересно
Автор конспекта: Константин Амеличев
По всем вопросам пишите в telegram @kik0s