Состояние любой структуры как-то лежит в памяти: в каких-то массивах, или в более общем случае, по каким-то определенным адресам в памяти. Для простоты, пусть у нас есть некоторый массив $a$ размера $n$, и нам нужно обрабатывать запросы присвоения и чтения, а также иногда откатывать изменения обратно.
#Список изменений
Один из самых простых и общих способов поддерживать простой откат состояний — поддерживать лог изменений всех затронутых элементов.
Если нужно только откатывать изменения до некоторого прошлого состояния (как “ctrl+z”), то можно просто создать стек, в котором будут храниться пары «какая ячейка изменилась, какое значение там было раньше», и для отката состояния пройтись по нему в обратном порядке, восстанавливая исходные значения.
int a[N];
stack< pair<int, int> > s;
void change(int k, int x) {
s.push({k, a[k]});
a[k] = x;
}
void rollback() {
while (!s.empty()) {
auto [k, x] = s.top();
a[k] = x;
s.pop();
}
}
Такой подход добавит небольшой константный оверхед на все операции, но позволит откатывать структуру — либо на какое-то на заданное изначальное состояние, либо на некоторое состояние в прошлом, если помимо позиции и значения хранить в стеке ещё и какую-то временную метку.
#Массив версий
Немного переформулируем задачу. Есть изначально нулевой массив $a$, и нужно поддерживать две операции:
- Сделать присвоение элемента $a[k] = x$.
- Занулить массив.
Задачу можно решить более элегантно. Заведем глобальный счетчик времени $t$ и изначально заполненный нулями массив версий $v$ такого же размера, как и $a$: в этом массиве будет храниться время, когда соответствующий элемент был в последний раз изменен.
int t = 1;
int a[N], v[N];
Условимся, что если версия элемента равна текущему времени $t$, то она корректная, иначе элемент равен нулю:
int get(int k) {
return (v[k] == t ? a[k] : 0);
}
Теперь, когда мы делаем присвоение элемента, мы обновляем его версию:
void change(int k, int x) {
a[k] = x;
v[k] = t;
}
Когда мы зануляем массив, мы просто инкрементируем счетчик $t$ и всё:
void rollback() {
t++;
}
Такой подход проще кодится и имеет меньший оверхед, однако немного менее применим.
#«Толстые» узлы
Пусть нам теперь нужно не откатывать изменения, а просто делать чтения каких-то элементов в прошлом. Список изменений нас не устраивает, потому что для каждого чтения в худшем случае потребуется просматривать $O(n)$ последних изменений.
Заведем список версий для каждого элемента, в конец которого будут складываться новые версии при каждом изменении, а также время этого изменения.
int t = 0;
vector< pair<int, int> > versions[N];
void change(int k, int x) {
versions[k].push_back({t++, x});
}
Тогда при чтении мы уже можем просматривать не все изменения, а только затрагивающие нужную ячейку. Но можно и ещё быстрее — элементы списка отсортированы по времени, а значит можно бинарным поиском найти последнее изменение, не превосходящее время из запроса:
int get(int k, int v) {
auto it = upper_bound(versions[k].begin(), versions[k].end(), v);
return (--it)->second;
}
Такое решение будет работать за $O(1)$ на изменение и $O(\log n)$ на запрос.
#Дерево изменений
Формально предыдущими методами мы достигли персистентности, но в весьма ограниченном смысле: мы не можем быстро откатываться до произвольной версии и делать «форк» из неё, при этом сохраняя все версии из «альтернативного будущего».
Эту проблему можно решить, храня радом с каждым изменением номер версии $p$, из которой произошел форк:
struct Node {
int k, x, p;
};
vector<Node> versions;
void change(int k, int x, int v) {
versions.push_back({k, x, v});
}
Тогда чтобы найти значение ячейки $k$ в момент времени $v$, нужно откатиться по этому массиву
int get(int k, int v) {
int res = 0;
for (int u = v; u > v; u = u = versions[u].p)
if (versions[u].k == k)
res = versions[u].x;
return res;
}
Такое решение реализует полноценный персистентный массив, но в худшем случае работает за $O(n)$.
Дерево изменений можно ускорить разными способами, обменяв время на память. Например, можно в некоторых нодах сохранять чекпойнты — полные массивы, соответствующие состоянию массива в этот момент времени.
Популярным конкретным способом это сделать является рандомизированное сохранение чекпойнтов на каждом запросе чтения — с вероятностью, пропорциональной дополнительной работе, которую нужно совершить, чтобы получить массив из следующего чекпойнта.