102
правки
Изменения
Нет описания правки
===Построение===
Для построения персистентного дерева отрезков из <tex>n</tex> элементов необходимо применить <tex>n</tex> раз операцию добавления элемента к последней версии деревапройтись по всему дереву, попутно создавая все необходимые вершины. Для тогоВ листах создавать вершину, чтобы добавить новый элемент к <tex>k</tex>-ой версии дерева, необходимо проверить, является ли оно полным бинарнымхранящую соответствующее значение. Если даПромежуточные же вершины строим от левого и правого сыновей treeBuild(a[], то создадим новый кореньtl, левым сыном сделаем <tex>rootstr) '''if''' tl == tr '''return''' '''new''' Vertex(a[ktl]<) tm = (tl + tr) /tex>. Иначе2 '''return''' '''new''' Vertex(treeBuild(a[], сделаем копию корня исходной версии. Добавим корень в конец массива корней. Далееtl, спускаясь от корня к первому свободному листуtm), будем создавать несуществующие узлы и клонировать существующие. После этого в новой ветке необходимо обновить значение функции и некоторые указатели дочерних элементов. Поэтому, возвращаясь из рекурсии, будем менять один указатель на только что созданную или скопированную вершину, а также обновим значение функцииtreeBuild(a[], для которой строилось дерево. После этой операции в дереве появится новая версияtm + 1, содержащая вставленный элемент.tr))
===Изменение элемента===
Здесь изображено персистентное дерево отрезков с операцией минимум, в котором изначально было 3 вершины. Сперва к нему была добавлена вершина со значением 2, а потом изменена вершина со значением 7. Цвет ребер и вершин соответствует времени их появления. Синий цвет элементов означает, что они были изначально, зеленый - что они появились после добавления, а оранжевый - что они появились после изменения элемента.
update(v, tl, tr, pos, val)
'''if''' tl == tr
'''return''' '''new''' Vertex(val)
tm = (tl + tr) / 2
'''if''' pos <= tm
'''return''' '''new''' Vertex(update(v.l, tl, tm, pos, val), v.r)
'''else'''
'''return''' '''new''' Vertex(v.l, update(v.r, tm + 1, tr, pos, val))
==См. также==
