Дерево отрезков. Построение

Дерево отрезков — это структура данных, которая позволяет за асимптотику [math]O(\log n)[/math] реализовать любые операции, определяемые на моноиде. Например, следующего вида: нахождение суммы (задача RSQ), минимума или максимума (задача RMQ) элементов массива в заданном отрезке ([math]a[i...j][/math], где [math]i[/math] и [math]j[/math] поступают на вход алгоритма)

При этом дополнительно возможно изменение элементов массива: как изменение значения одного элемента, так и изменение элементов на целом подотрезке массива, например разрешается присвоить всем элементам [math]a[i...j][/math] какое-либо значение, либо прибавить ко всем элементам массива какое-либо число. Структура занимает [math]O(n)[/math] памяти, а ее построение требует [math]O(n)[/math] времени.

Структура

Структура представляет собой дерево, листьями которого являются элементы исходного массива. Другие вершины этого дерева имеют по 2 ребёнка и содержат результат операции от своих детей (например минимум или сумму). Таким образом, корень содержит результат искомой функции от всего массива [math][0...n-1][/math], левый ребёнок корня содержит результат функции на [math][0...n/2][/math], а правый, соответственно результат на [math][n/2+1...n-1][/math]. И так далее, продвигаясь вглубь дерева.

Построение дерева

Пусть исходный массив [math]a[/math] состоит из [math]n[/math] элементов. Для удобства построения увеличим длину массива [math]a[/math] так, чтобы она равнялась ближайшей степени двойки, т.е. [math]2^k[/math], где [math]2^k \ge n[/math]. Это сделано, для того чтобы не допустить обращение к несуществующим элементам массива при дальнейшем процессе построения. Пустые элементы необходимо заполнить нейтральными элементами моноида. Тогда для хранения дерева отрезков понадобится массив [math]t[/math] из [math]2^{k+1}[/math] элементов, поскольку в худшем случае количество вершин в дереве можно оценить суммой [math]n+n/2+n/4...+1 \lt 2n[/math], где [math]n=2^k[/math]. Таким образом, структура занимает линейную память.

Процесс построения дерева заключается в заполнении массива [math]t[/math]. Заполним этот массив таким образом, чтобы [math]i[/math]-й элемент являлся бы значением функции (для каждой конкретной задачи своей) от элементов c номерами [math]2i+1[/math] и [math]2i+2[/math], то есть родитель являлся значением функции своих сыновей. Один из вариантов — делать рекурсивно. Пусть у нас имеются исходный массив [math]a[/math], а также переменные [math]tl[/math] и [math]tr[/math], обозначающие границы текущего полуинтервала. Запускаем процедуру построения от корня дерева отрезков ([math]i=0[/math], [math]tl=0[/math], [math]tr=n[/math]), а сама процедура построения, если её вызвали не от листа, вызывает себя от каждого из двух сыновей и суммирует вычисленные значения, а если её вызвали от листа — то просто записывает в себя значение этого элемента массива (Для этого у нас есть исходный массив [math] a [/math]). Асимптотика построения дерева отрезков составит, таким образом, [math]O(n)[/math].

Выделяют два основных способа построения дерева отрезков: построение снизу и построение сверху. При построении снизу алгоритм поднимается от листьев к корню (Просто начинаем заполнять элементы массива [math]t[/math] от большего индекса к меньшему, таким образом при заполнении элемента [math] i [/math] его дети [math]2i+1[/math] и [math]2i+2[/math] уже будут заполнены, и мы с легкостью посчитаем функцию от них), а при построении сверху спускается от корня к листьям. Особенные изменения появляются в реализации запросов к таким деревьям отрезков.

Реализация построения сверху:

TreeBuild(a[], i, tl, tr)
// Мы находимся в элементе с номером i, который отвечает за полуинтервал [tl, tr)
 if (tl = tr) return;
 if (tr - tl = 1)
    t[i] = a[tl];
 else
    tm = (tl + tr) / 2; //середина отрезка
    TreeBuild(a, 2 * i + 1, tl, tm);
    TreeBuild(a, 2 * i + 2, tm, tr);
    t[i] = f(t[2 * i + 1], t[2 * i + 2]);

Реализация построения снизу:

TreeBuild(a[])
 for i = n - 1 .. 2 * n - 1
  t[i] = a[i - n - 1]
 for i = n - 2 .. 0
  t[i] = f(t[2 * i + 1], t[2 * i + 2])

Персистентное дерево отрезков

Определение:

Персистентной (англ. Persistent) называется такая структура данных, которая хранит все свои промежуточные версии.

Определение:

Полностью персистентной (англ. Fully persistent) называется такая персистентная структура данных, в которой разрешено изменять любую её версию и делать запросы к любой её версии.

На основе дерева отрезков можно построить полностью персистентную структуру данных.

Структура дерева

Для реализации персистентного дерева отрезков удобно несколько изменить структуру дерева. Для этого будем использовать явные указатели [math]L[/math] и [math]R[/math] для дочерних элементов и [math]P[/math] для родительского узла. Кроме того, заведем массив [math]roots[][/math], в котором [math]roots[i][/math] указывает на корень дерева отрезков версии [math]i[/math]

Построение

Для построения персистентного дерева отрезков из [math]n[/math] элементов необходимо применить [math]n[/math] раз операцию добавления элемента к последней версии дерева. Для того, чтобы добавить новый элемент к [math]k[/math]-ой версии дерева, необходимо проверить, является ли оно полным бинарным. Если да, то создадим новый корень, левым сыном сделаем [math]roots[k][/math]. Иначе, сделаем копию корня исходной версии. Добавим корень в конец массива корней. Далее, спускаясь от корня к первому свободному листу, будем создавать несуществующие узлы и клонировать существующие, изменяя указатель на родителя на предыдущий созданный узел. После этого в новой ветке необходимо обновить значение функции и некоторые указатели дочерних элементов. Поэтому, возвращаясь из рекурсии, будем менять один указатель на только что созданную или скопированную вершину, а также обновим значение функции, для которой строилось дерево. После этой операции в дереве появится новая версия, содержащая вставленный элемент.

Изменение элемента

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

Псевдокод


 addElement (Tree, ver, x)
   if Tree.isFullBinary(ver)
     Node tmpRoot = new Node();
     roots[Tree.countOfVersions++ + 1] = recAdd(tmpRoot, null, 0, 2 * Tree.size(ver), x, Tree.size(ver) + 1); 
   else 
     // k : 2 ^ (k - 1) <= Tree.size(ver) < 2 ^ k
     roots[Tree.countOfVersions++ + 1] = recAdd(roots[ver], null, 0, 2 ^ k, x, Tree.size(ver) + 1);
 
 Node recAdd (node, parent, l, r, x, n)
   // Мы находимся в узле node, который отвечает за полуинтервал (l, r]
   if r - l == 1
     return new Node(parent, x)
   m = (l + r) / 2;
   if node == null
     Node tmp = new Node(parent);
     node = tmp;
   else 
     Node tmp = node.clone();
     tmp.parent = parent;
   if n <= m
     tmp.L = recAdd(node.L, tmp, l, m, x, n);
   else 
     tmp.R = recAdd(node.R, tmp, m, r, x, n);
   tmp.valueOfFunction = f(tmp.L, tmp.R);
   return tmp;

 Node change (Tree, parent, node, l, r, i, x)
   //изменить i-ый элемент на x
   if r - l == 1
     return new Node(x);
   else
     m = (l + r) / 2;
     Node tmp = node.clone();
     tmp.parent = parent;
     if i <= m
       tmp.L = change(Tree, tmp, node.L, l, m, i, x);
     else
       tmp.R = change(Tree, tmp, node.R, m, r, i, x);
     tmp.valueOfFunction = f(tmp.L, tmp.R);
     if(node.parent == null)
       roots[Tree.countOfVersions++ + 1] = tmp;
     return tmp;

Здесь функции [math]recAdd()[/math] и [math]change()[/math] возвращает указатель на узел новой ветки.