Изменения
→Получение полностью персистентных структур данных
В ''change log'' «толстого» узла теперь будем добавлять два события: одно указывает на изменение, произошедшее в соответствующей версии, а другое на его отмену. События будут добавляться в ''change log'' не по номерам версий, а по их порядку в списке версий ''List Order Maintenance''.
Когда есть запрос к какой-то версии, то нужно найти в списке версий такую, после входа в которую, но до выхода из которой лежит версия запроса, а среди таких максимальную. Нужно идти от головы списка до нужной версии и необходимо знать, куда переходить в каждый момент. Например, если приходит запрос к версии <tex>6</tex> на рисунке выше, то мы видим, что она в списке версий лежит после входа, но до выхода в версии <tex>1</tex>, <tex>2</tex> и <tex>4</tex>. Необходимо найти наибольшую из них. Список ''List Order Maintenance'' позволяет делать это за <tex>O(1)</tex> с помощью операции <tex>\mathrm{order(p,q)}</tex>. В примере это версия <tex>4</tex>. Так как ''change log'' каждого узла имеет константный размер, то поиск нужной версии в нем происходит за <tex>O(1)</tex>.
В какой-то момент ''change log'' «толстого» узла переполнится. Тогда нужно клонировать этот узел и нижнюю половину изменений перенести в ''change log'' склонированного узла. Первую половину изменений применяем к исходной версии узла и сохраняем в качестве исходной в склонированном узле.
