main.cpp содержит класс UniversalArray, реализованный на АВЛ-дереве по неявному ключу, с реализованными операциями find, insert, remove, split, merge, reverse, с возможностью присвоения и прибавления на отрезке и запросов суммы, минимума и максимума на отрезке.
Сам main.cpp способен отвечать на запросы:
v pos value - вставка value на позицию pos
x pos - удаление элемента на позиции pos
. pos - вывод значения элемента на позиции pos
= left right value - присвоение value на отрезке от left до right
+ left right value - прибавление value на отрезке от left до right
? left right - вывести сумму, минимум и максимум на отрезке от left до right
r left right - перевернуть отрезок от left до right
exit - выход
left, right, pos должны быть в 0-индексации. Изначально массив пустой.
Реализация аналогичной структуры данных, в которой, в отличие от реализации в main.cpp, для узлов не хранится родитель узла. Это сделано для того, чтобы в дальнейшем было легче преобразовать структуру данных в персистентную.
По сравнению с main.cpp полностью по-другому переписаны некоторые функции, большинство из них теперь написаны рекурсивно, в некоторых случаях добавлены вспомогательные рекурсивные функции.
persistent1.cpp содержит класс PUA (PersistentUniversalArray), представляющий собой персистентное АВЛ-дерево по неявному ключу с возможностью отвечать на следующие запросы на массиве (изначально пустом):
v pos value - вставка value на позицию pos
x pos - удаление элемента на позиции pos
. pos - вывод значения элемента на позиции pos
= left right value - присвоение value на отрезке от left до right
+ left right value - прибавление value на отрезке от left до right
? left right - вывести сумму, минимум и максимум на отрезке от left до right
r left right - перевернуть отрезок от left до right
c id - рассмотреть версию, получившуюся после запроса с индексом id (в 0-индексации, id = -1 означает исходную версию до всех запросов)
exit - выход
left, right, pos, id должны быть в 0-индексации.