\Section{Дерево отрезков.}{26 февраля}{Богомолов Егор}

\Subsection{Еще немножко о деревьях поиска.}

Раньше, если нам хотелось посчитать какую-нибудь функцию на отрезке значений, лежащих в дереве поиска, мы умели вырезать этот отрезок при помощи двух операций split, брать значение функции в корне и склеивать дерево двумя merge'ами обратно. У этого способа много проблем --- split и merge возможны далеко не всегда, к тому же, 4 вызова этих функций ради одного отрезка --- дорогое удовольствие.

Напишем простой код для этой задачи, считая, что функция --- сумма на отрезке, а потом поймем, почему он хорошо работает:

\begin{code} 
int get (Node v, Query q) {
	if (q in v)
		return v.sum;
	if (q not in v)
		return 0;
	return  get(v.l, q) + v.value + get(v.r, q);
}
\end{code}

Если вершина целиком в запросе или вне него --- сразу вернем ответ. Если же она пересекается с запросом, просто вызовемся от ее детей.

Рассмотрим все вершины, лежащие на одной глубине. Если рассматривать их слева направо, то они лежат так:

\begin{MyList}
  \item вне запроса
  \item пересекаются с запросом (не более 1 вершины)
  \item в запросе
  \item пересекаются с запросом (не более 1 вершины)
  \item вне запроса
\end{MyList}

На нулевой глубине лежит ровно одна вершина --- корень. Из написанного выше списка видно, что на каждом следующем уровне будет задействованно не более 4 вершин (новые вызовы порождаются не более чем 2 вершинами). Итого, если глубина дерева h, суммарно запрос отработает за $\O(4h) = \O(h)$.

\Subsection{Самые обычные деревья отрезков.}

Дерево отрезков --- структура данных, строящаяся над массивом или его подобием и позволяющая делать кучу всяких полезных вещей. Например, считать на отрезке значение любой ассоциативной функции.

Что оно вообще из себя представляет? Будем считать, что мы работаем с массивом $a[]$, $size(a) = 2^k = n$, если это не так --- добьем до степени двойки нейтральными элементами функции, которую хотим считать. Для дерева отрезков понадобится второй массив $tree[]$, $size(tree) = 2n$. В нем вершины $[n..2n)$ будут листьями и будут соответствовать оригинальному массиву. Как и в бинарной куче, для вершины с индексом $i$ детьми будут $2i$ и $2i + 1$. Родителем, соотетственно, будет $\frac{i}{2}$. Каждая вершина отвечает за отрезок листьев, находящихся в ее поддереве.

Приведем код построения ДО (опять функцией для простоту выберем сумму, а элементами --- целые числа):

\begin{code}
void init(int* a, int* tree, int n) {
	tree = new int[2 * n];
	copy(a, a + n, tree + n);
	for(i = n - 1; i > 0; --i) {
		tree[i] = tree[2 * i] + tree[2 * i + 1];
	}
}
\end{code}

Построить дерево смогли, как делать в нем запросы на отрезке, мы уже знаем. Теперь хочется поменять какой-нибудь элемент. Для изменения отдельного элемента есть два подхода --- сверху и снизу. Сверху --- запускаемся от корня, спускаемся в лист, изменяем в нем значение и на обратном ходе рекурсии пересчитываем значение в вершинах. Снизу --- поднимаемся (без рекурсии, просто в цикле) от листа к корню и пересчитываем значения в вершинах. Второй способ короче с точки зрения кода, побыстрее работает, но не позволяет делать операций изменения на отрезке, что немаловажно.

Сверху (вершина $v$ отвечает за отрезок $[L..R)$, хотим в $pos$ записать $x$):

\begin{code}
void change(int v, int L, int R, int pos, int x) {
	if (L + 1 == R) {
		tree[v] = x;
		return;
	}
	int middle = (L + R) / 2;
	if (pos < middle)
		change(2 * v, L, middle, pos, x);
	else 
		change(2 * v + 1, middle, R, pos, x);
	tree[v] = tree[2 * v] + tree[2 * v + 1]; 	
}
\end{code}

Снизу:

\begin{code}
void change(int pos, int x) {
	tree[pos] = x;
	pos /= 2;
	while (pos > 0) {
		tree[pos] = tree[2 * pos] + tree[2 * pos + 1]; 
		pos /= 2;	
	}
}
\end{code}

get сверху уже описан сверху (sic!). Напишем get снизу (те же преимущества, что и у изменения снизу):

\begin{code}
int get(int L, int R) {
	int sum = 0;
	for(L += n, R += n; L <= R; L /= 2, R /= 2) {
		if (L $%$ 2 == 1) sum += tree[L++];
		if (R $%$ 2 == 1) sum += tree[R--]; 
	}
	return sum;
}
\end{code}

На этом обычные деревья отрезков заканчиваются и начинаются интересности.

\subsection{Динамическое ДО.}

Пока что массив был достаточно коротким, чтобы помещаться в память целиком. А что, если хотим работать с массивом длины $10^9$ или $10^{18}$, в котором не очень много элементов, отличных от нейтрального? Опять появляются два подхода.

Если решаем задачу offline, то можно сжать координаты --- отсортировать все позиции, которые будут встречаться в запросах и работать только с ними.

Если решаем задачу online, то на помощь приходит динамическое дерево отрезков. Изначально в нем есть только корень, отвечающий за весь массив. Когда поступают запросы, мы при необходимости создаем новые вершины. Т.е., если мы хотим пойти в вершину, которой нет, создаем ее. Теперь дерево приходится писать не на массиве, а на указателях. Время работы тоже меняется, теперь это не $\O(\log n)$, а $\O(\log C)$, где $C$ --- максимальное значение, которое нам может встретиться.

С динамическим ДО, в принципе, можно работать снизу, но это не особо интересно даже в теории, разве что как игра ума.

\subsection{Персистентное ДО.}

Не отличается от других персистентных структур. Вместо изменения вершины, создаем ее копию и работаем с ней. Теперь уж точно приходится писать ДО на указателях и работать с ним сверху. Позволяет реализовать персистентный массив, а он в свою очередь --- персистентное много что.

В общем случае код функции будет выглядеть как-то так:

\begin{code}
Node* foo(Node* u, ..) {
	Node *v = new Node(u);
	...
	if (...)
		v->left = foo(v->left, ..);
	else
		v->right = foo(v->right, ..)	
	...
	return v;
}
\end{code}

\subsection{Многомерные ДО.}

Пока что в вершинах лежали какие-то значения. Но этим можно не ограничиваться --- в них можно сохранить все что угодно. Если сохранить в них какую-нибудь другую структуру данных, например еще одно ДО или ДД, то получится двумерное ДО. Вложенность можно делать какую угодно, главное понимать зачем.

Для примера сохраним в вершине отсортированный массив значений ее отрезка. Строится такое ДО точно так же, как и обычное, благодаря встроенному merge: 
\begin{code}
merge(tree[2 * i].begin(), tree[2 * i].end(), tree[2 * i + 1].begin(), tree[2 * i + 1].end(), tree[i].begin());
\end{code}
Такое дерево может, например, считать количество чисел со значениями из $[A..B]$ на отрезке индексов $[L..R)$. Для этого приходя в вершину считаем искомое число двумя бинпоисками на ее массиве.
