Структуры с откатами - Алгоритмика
Структуры с откатами

Структуры с откатами

автор Сергей Слотин
обновлено сент. 12, 2021

Состояние любой структуры как-то лежит в памяти: в каких-то массивах, или в более общем случае, по каким-то определенным адресам в памяти. Для простоты, пусть у нас есть некоторый массив $a$ размера $n$, и нам нужно обрабатывать запросы присвоения и чтения, а также иногда откатывать изменения обратно.

#Список изменений

Один из самых простых и общих способов поддерживать простой откат состояний — поддерживать лог изменений всех затронутых элементов.

Если нужно только откатывать изменения до некоторого прошлого состояния (как “ctrl+z”), то можно просто создать стек, в котором будут храниться пары «какая ячейка изменилась, какое значение там было раньше», и для отката состояния пройтись по нему в обратном порядке, восстанавливая исходные значения.

int a[N];

stack< pair<int, int> > s;

void change(int k, int x) {
    l.push({k, a[k]});
    a[k] = x;
}

void rollback() {
    while (!s.empty()) {
        auto [k, x] = s.top();
        a[k] = x;
        s.pop();
    }
}

Такой подход добавит небольшой константный оверхед на все операции, но позволит откатывать структуру — либо на какое-то на заданное изначальное состояние, либо на некоторое состояние в прошлом, если помимо позиции и значения хранить в стеке ещё и какую-то временную метку.

#Массив версий

Немного переформулируем задачу. Есть изначально нулевой массив $a$, и нужно поддерживать две операции:

  1. Сделать присвоение элемента $a[k] = x$.
  2. Занулить массив.

Задачу можно решить более элегантно. Заведем глобальный счетчик времени $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<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)$.

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

Популярным конкретным способом это сделать является рандомизированное сохранение чекпойнтов на каждом запросе чтения — с вероятностью, пропорциональной дополнительной работе, которую нужно совершить, чтобы получить массив из следующего чекпойнта.