Изменения

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

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

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

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