Изменения

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