Персистентные структуры данных

Обычная структура данных живёт в одном экземпляре. Изменили дерево отрезков — прежнего состояния больше нет; разрезали и склеили декартово дерево — того, что было до, не восстановить.

Персистентная структура хранит все свои версии. Каждое изменение не портит старое состояние, а создаёт новое, и обратиться можно к любому.

	обычная	персистентная
изменение	портит текущее состояние	создаёт новую версию
старые версии	недоступны	доступны все
память на изменение	$O(1)$	$O(\log n)$
откуда расти	только из текущего состояния	из любой версии

Последняя строка отличает персистентность от «сохранить копию и откатиться». Версии образуют не цепочку, а дерево: из одной версии могут вырасти несколько разных, и все они остаются живыми.

Три уровня

В литературе различают три степени:

уровень	что можно
частичная	читать все версии, менять только последнюю
полная	читать все версии и менять любую
конфлюэнтная	ещё и сливать две версии в одну

Всё, что обычно нужно на олимпиаде, — полная персистентность для деревьев, и она получается почти даром. Общая теория (Дрисколл, Сарнак, Слейтор и Тарьян, 1986) умеет делать частично персистентной любую структуру с ограниченной степенью узла за $O(1)$ дополнительной памяти на изменение.

Главная идея: путь вместо копии

Копировать структуру целиком на каждое изменение — $O(n)$ памяти на операцию: при $n = q = 10^5$ это $10^{10}$ чисел, что невозможно.

Но копировать всё и не нужно. В дереве изменение затрагивает один путь от корня до листа. Всё, что вне этого пути, у старой и новой версии одинаково — и может быть общим:

   старый корень      новый корень
        │                   │
        ├── A ───────────── │        A общий
        └── B          новый B
             ├── C ──────── │        C общий
             └── D     новый D

Новая версия — это $O(\log n)$ новых узлов плюс ссылки на чужие поддеревья. Отсюда правило, которое объясняет всё остальное:

Персистентно то, что можно перестроить по одному пути. Дерево — можно. Массив — нет, поэтому массив сначала превращают в дерево.

Обратная сторона: узлы общие. Ни один узел нельзя менять на месте, иначе изменится не одна версия, а неизвестно сколько.

Списки: персистентность сама собой

Односвязный список персистентен по построению, если операции ничего не переписывают.

Стек — список от вершины вниз, версия — указатель на узел:

int push(int version, int value) {
    int node = used++;
    down[node] = version;
    item[node] = value;
    return node;                    // новая версия
}
int top(int version) { return item[version]; }
int pop(int version) { return down[version]; }   // и это всё

pop ничего не удаляет: он возвращает указатель на то, что было раньше. Память — $O(1)$ на операцию, а не $O(\log n)$: это дешевле общего случая, потому что «путь» здесь состоит из одного узла.

Очередь: где ломается и чем чинится

У очереди добавляют с одного конца, а берут с другого. Хвост наращивается как стек, а голова оказывается в глубине списка: до неё столько шагов, сколько элементов в очереди. Наивный проход — $O(n)$ на запрос.

Чинится двоичными подъёмами: у каждого узла храним предков на расстояниях $1, 2, 4, \ldots$

up[node][0] = version;
for (int level = 1; level < LOG; level++) up[node][level] = up[ up[node][level - 1] ][level - 1];

Прыжок на $k$ шагов вниз разбирается по битам $k$ — $O(\log n)$. Это тот же приём, что для наименьшего общего предка, только дерево здесь — история версий, а не дерево из условия.

Память: $O(\log n)$ на узел. Если версий $2 \cdot 10^5$, а $\text{LOG} = 18$, это $3.6 \cdot 10^6$ чисел — приемлемо, но заметно, и об этом стоит помнить.

Числовая характеристика версии

Часто про версию спрашивают не содержимое, а число: сумму, размер, максимум. Такие величины обычно считаются за $O(1)$ от родительской версии и хранятся в отдельном массиве:

sum[node] = sum[parent] + value;
best[node] = std::max(best[parent], value);

Структура при этом нужна только ради содержимого, а ответы на «числовые» запросы берутся из массива напрямую. Полезно замечать это до того, как написано дерево: половина задач про версии решается одним массивом.

Персистентность или откат

Если версии не ветвятся — то есть все обращения идут к текущему состоянию, а «назад» означает «отменить последнее», — персистентность избыточна. Достаточно отката: стек изменений, каждое из которых умеет отменяться.

	откат	персистентность
доступ к прошлому	только назад по одному	к любой версии сразу
ветвление версий	нет	есть
память	$O(1)$ на операцию	$O(\log n)$ на операцию
сложность реализации	низкая	средняя

Классический пример отката — система непересекающихся множеств без сжатия путей: объединение по размеру меняет одну ссылку и один размер, оба кладутся в стек. На этом стоит разделяй-и-властвуй по времени для динамической связности.

Чек-лист

1. Обращаются ли к прошлым состояниям вообще? Если нет — обычная структура.
2. Ветвятся ли версии? Если нет — хватит отката.
3. Спрашивают число или содержимое? Число часто считается от родителя за $O(1)$.
4. Можно ли отсортировать запросы? Если да — офлайн-решение обычно короче.

Смежное: персистентное дерево отрезков, дерево отрезков, система непересекающихся множеств.