142
правки
Изменения
→Получение полностью персистентных структур данных
Получится два узла: первый отвечает за отрезок версий до операции последнего изменения, а второй после нее. Дальнейший порядок действий аналогичен тому, который использовался в общем методе построения частично персистентных структур данных.
Оценим амортизационное время работы этого алгоритма. Введем потенциалфункцию потенциала, равный суммарному размеру нижних половин списков изменений во всех версияхравную числу полных узлов. Когда мы раздваиваем узелраздваивается, мы уменьшаем потенциал функция потенциала уменьшается на половину размера списка изменений (в нашем примере это <tex>2P</tex>)единицу, затем мы переставляем <tex>P</tex> ссылок, потенциал увеличивается на <tex>P</tex>, значит амортизационное время работы — <tex>O(1)</tex>.
==Использование персистентных структур данных для решения геометрических задач==
