Дерево отрезков. Построение
Дерево отрезков — это структура данных, которая позволяет за асимптотику реализовать любые операции, определяемые на моноиде. Например, следующего вида: нахождение суммы (задача RSQ), минимума или максимума (задача RMQ) элементов массива в заданном отрезке (, где и поступают на вход алгоритма)
При этом дополнительно возможно изменение элементов массива: как изменение значения одного элемента, так и изменение элементов на целом подотрезке массива, например разрешается присвоить всем элементам какое-либо значение, либо прибавить ко всем элементам массива какое-либо число. Структура занимает памяти, а ее построение требует времени.
Структура
Структура представляет собой дерево, листьями которого являются элементы исходного массива. Другие вершины этого дерева имеют по 2 ребёнка и содержат результат операции от своих детей (например минимум или сумму). Таким образом, корень содержит результат искомой функции от всего массива , левый ребёнок корня содержит результат функции на , а правый, соответственно результат на . И так далее, продвигаясь вглубь дерева.
Построение дерева
Пусть исходный массив состоит из элементов. Для удобства построения увеличим длину массива так, чтобы она равнялась ближайшей степени двойки, т.е. , где . Это сделано, для того чтобы не допустить обращение к несуществующим элементам массива при дальнейшем процессе построения. Пустые элементы необходимо заполнить нейтральными элементами моноида. Тогда для хранения дерева отрезков понадобится массив из элементов, поскольку в худшем случае количество вершин в дереве можно оценить суммой , где . Таким образом, структура занимает линейную память.
Процесс построения дерева заключается в заполнении массива . Заполним этот массив таким образом, чтобы -й элемент являлся бы значением функции (для каждой конкретной задачи своей) от элементов c номерами и , то есть родитель являлся значением функции своих сыновей. Один из вариантов — делать рекурсивно. Пусть у нас имеются исходный массив , а также переменные и , обозначающие границы текущего полуинтервала. Запускаем процедуру построения от корня дерева отрезков (, , ), а сама процедура построения, если её вызвали не от листа, вызывает себя от каждого из двух сыновей и суммирует вычисленные значения, а если её вызвали от листа — то просто записывает в себя значение этого элемента массива (Для этого у нас есть исходный массив ). Асимптотика построения дерева отрезков составит, таким образом, .
Выделяют два основных способа построения дерева отрезков: построение снизу и построение сверху. При построении снизу алгоритм поднимается от листьев к корню (Просто начинаем заполнять элементы массива от большего индекса к меньшему, таким образом при заполнении элемента его дети и уже будут заполнены, и мы с легкостью посчитаем функцию от них), а при построении сверху спускается от корня к листьям. Особенные изменения появляются в реализации запросов к таким деревьям отрезков.
Реализация построения сверху:
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])
Персистентное дерево отрезков
| Определение: |
| Персистентной называется такая структура данных, которая хранит все свои промежуточные версии. |
| Определение: |
| Полностью персистентной называется такая персистентная структура данных, что разрешено изменять любую её версию и делать запросы к любой её версии. |
На основе дерева отрезков можно построить полностью персистентную структуру данных.
Структура
Для реализации персистентного дерева отрезков удобно несколько изменить структуру дерева:
- будем использовать явные указатели и для дочерних элементов и для родительского узла
- заведем массив , в котором указывает на корень дерева отрезков версии
Построение
Для построения персистентного дерева отрезков из элементов необходимо применить раз операцию добавления элемента к последней версии дерева. Для того, чтобы добавить новый элемент к -ой версии дерева необходимо проверить является ли оно полным бинарным. Если да, то создадим новый корень, левым сыном сделаем . Иначе, оставим корень таким же, как и в исходной версии. Далее, спускаясь от корня к первому свободному листу, будем создавать несуществующие узлы и клонировать существующие, изменяя указатель на родителя предыдущим созданным узлом. После этого в новой ветке необходимо обновить значение функции и некоторые указатели дочерних элементов. Поэтому, возвращаясь из рекурсии, будем менять один указатель на только что созданную или скопированную вершину, а также обновим значение функции. После этой операции в дереве появится новая версия, содержащая вставленный элемент.
Изменение
Воспользуемся аналогичной схемой, что и при вставке элемента. Для этого найдем в дереве требуемый элемент, скопируем его, изменим значение, и, поднимаясь по дереву, будем клонировать узлы, меняя один из указателей и пересчитывая значение функции. Новый корень добавим в список корней.
