Изменения
→Получение полностью персистентных структур данных
Для реализации описанного в предыдущем пункте метода преобразования структур данных в полностью персистентные нам нужен такой список, который поддерживает операции ''«insert after»'' и ''«order»''. Обе операции нужно делать за <tex>O(1</tex>). Это список с поддержкой запроса о порядке ''List Order Maintenance'' <ref>[http://www.cs.au.dk/~gerth/aa11/slides/order.pdf]</ref>.
Операция обновления в этом списке будет происходить так: в список версий добавляется два элемента – — первый вносит изменение, а второй будет возвращать обратно значение предыдущей версии. Таким образом, каждая операция разбивается на две: первая делает изменение, а вторая его откатывает.
В ''change log'' «толстого» узла теперь будем добавлять два события: одно указывает на изменение, произошедшее в соответствующей версии, а другое на его отмену. События будут отсортированы по их порядку в списке версий с помощью ''List Order Maintenance''.
В какой-то момент ''change log'' «толстого» узла переполнится. Тогда нужно клонировать этот узел и нижнюю половину изменений перенести в ''change log'' склонированного узла. Первую половину изменений применяем к исходной версии узла и сохраняем в качестве исходной в склонированном узле.
Оценим амортизационное время работы этого алгоритма. Введем потенциал, равный суммарному размеру нижних половин списков изменений во всех версиях. Когда мы раздваиваем узел, мы уменьшаем потенциал на половину размера списка изменений (в нашем примере это <tex>2P</tex>), затем мы переставляем <tex>P</tex> ссылок, потенциал увеличивается на <tex>P</tex>, значит амортизационное время работы - <tex>O(1)</tex>.
==Использование персистентных структур данных для решения геометрических задач===
