Для того, чтобы изменить элемент в персистентном дереве отрезков, необходимо сделать следующие действия: найдем в дереве требуемый элемент, скопируем его, изменим значение, и, поднимаясь по дереву, будем клонировать узлы. При этом необходимо менять указатель на одного из детей на узел, созданный при предыдущем клонировании. После копирования корня, добавим новый корень в конец массива корней.
===Псевдокод===
<code>
addElement (Tree, ver, x)
if Tree.isFullBinary(ver)
Node tmpRoot = new Node();
roots[Tree.countOfVersions++ + 1] = recAdd(tmpRoot, null, 0, 2 * Tree.size(ver), x, Tree.size(ver) + 1);
else
// k : 2 ^ (k - 1) <= Tree.size(ver) < 2 ^ k
roots[Tree.countOfVersions++ + 1] = recAdd(roots[ver], null, 0, 2 ^ k, x, Tree.size(ver) + 1);
Node recAdd (node, parent, l, r, x, n)
// Мы находимся в узле node, который отвечает за полуинтервал (l, r]
if r - l == 1
return new Node(parent, x)
m = (l + r) / 2;
if node == null
Node tmp = new Node(parent);
node = tmp;
else
Node tmp = node.clone();
tmp.parent = parent;
if n <= m
tmp.L = recAdd(node.L, tmp, l, m, x, n);
else
tmp.R = recAdd(node.R, tmp, m, r, x, n);
tmp.valueOfFunction = f(tmp.L, tmp.R);
return tmp;
Node change (Tree, parent, node, l, r, i, x)
//изменить i-ый элемент на x
if r - l == 1
return new Node(x);
else
m = (l + r) / 2;
Node tmp = node.clone();
tmp.parent = parent;
if i <= m
tmp.L = change(Tree, tmp, node.L, l, m, i, x);
else
tmp.R = change(Tree, tmp, node.R, m, r, i, x);
tmp.valueOfFunction = f(tmp.L, tmp.R);
if(node.parent == null)
roots[Tree.countOfVersions++ + 1] = tmp;
return tmp;
</code>
Здесь функции <tex>recAdd()</tex> и <tex>change()</tex> возвращает указатель на узел новой ветки.
[[Файл:persist.png]]
