Дерево отрезков

Задача

Нам дан массив $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)$.

Вот тут в какой-то момент появится реализация дерева отрезков

Массовые операции

Мы уже решили исходную задачу, поэтому давайте просто дополним статью еще несколькими трюками. Если в задаче нам требуется делать какую-то операцию на отрезке (например, присвоить всем элементам значение $x$), то мы будем находить соответствующие вершины, и в них пользоваться техникой отложенных операций.

---

Автор конспекта: Константин Амеличев

По всем вопросам пишите в telegram @kik0s