Дерево отрезков. Построение — различия между версиями
Loboda.A (обсуждение | вклад) м (→Построение) |
Loboda.A (обсуждение | вклад) м (→Построение) |
||
Строка 52: | Строка 52: | ||
===Построение=== | ===Построение=== | ||
− | Для построения персистентного дерева отрезков из <tex>n</tex> элементов необходимо применить <tex>n</tex> раз операцию добавления элемента к последней версии дерева. Для того, чтобы добавить новый элемент к <tex>k</tex>-ой версии дерева необходимо проверить является ли оно полным бинарным. Если да, то создадим новый корень, левым сыном сделаем <tex>roots[k]</tex>. Иначе, оставим корень таким же, как и в исходной версии. Далее, спускаясь от корня к первому свободному листу, будем создавать несуществующие узлы и клонировать существующие, | + | Для построения персистентного дерева отрезков из <tex>n</tex> элементов необходимо применить <tex>n</tex> раз операцию добавления элемента к последней версии дерева. Для того, чтобы добавить новый элемент к <tex>k</tex>-ой версии дерева необходимо проверить является ли оно полным бинарным. Если да, то создадим новый корень, левым сыном сделаем <tex>roots[k]</tex>. Иначе, оставим корень таким же, как и в исходной версии. Далее, спускаясь от корня к первому свободному листу, будем создавать несуществующие узлы и клонировать существующие, изменяя указатель на родителя на предыдущий созданный узел. После этого в новой ветке необходимо обновить значение функции и некоторые указатели дочерних элементов. Поэтому, возвращаясь из рекурсии, будем менять один указатель на только что созданную или скопированную вершину, а также обновим значение функции поместим новый корень в список корней. После этой операции в дереве появится новая версия, содержащая вставленный элемент. |
===Изменение=== | ===Изменение=== |
Версия 08:49, 1 июня 2013
Дерево отрезков — это структура данных, которая позволяет за асимптотику моноиде. Например, следующего вида: нахождение суммы (задача 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])
Персистентное дерево отрезков
Определение: |
Персистентной называется такая структура данных, которая хранит все свои промежуточные версии. |
Определение: |
Полностью персистентной называется такая персистентная структура данных, что разрешено изменять любую её версию и делать запросы к любой её версии. |
На основе дерева отрезков можно построить полностью персистентную структуру данных.
Структура
Для реализации персистентного дерева отрезков удобно несколько изменить структуру дерева:
- будем использовать явные указатели и для дочерних элементов и для родительского узла
- заведем массив , в котором указывает на корень дерева отрезков версии
Построение
Для построения персистентного дерева отрезков из
элементов необходимо применить раз операцию добавления элемента к последней версии дерева. Для того, чтобы добавить новый элемент к -ой версии дерева необходимо проверить является ли оно полным бинарным. Если да, то создадим новый корень, левым сыном сделаем . Иначе, оставим корень таким же, как и в исходной версии. Далее, спускаясь от корня к первому свободному листу, будем создавать несуществующие узлы и клонировать существующие, изменяя указатель на родителя на предыдущий созданный узел. После этого в новой ветке необходимо обновить значение функции и некоторые указатели дочерних элементов. Поэтому, возвращаясь из рекурсии, будем менять один указатель на только что созданную или скопированную вершину, а также обновим значение функции поместим новый корень в список корней. После этой операции в дереве появится новая версия, содержащая вставленный элемент.Изменение
Воспользуемся аналогичной схемой, что и при вставке элемента. Для этого найдем в дереве требуемый элемент, скопируем его, изменим значение, и, поднимаясь по дереву, будем клонировать узлы, меняя один из указателей и пересчитывая значение функции. Новый корень добавим в список корней.
Псевдокод
Ссылки
- Визуализатор дерева отрезков