Откатывание состояний

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

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

#Корневая эвристика по запросам

Рассмотрим стандартную задачу: есть массив размера $n$, и требуется выполнять $q$ запросов прибавления на отрезке и суммы на отрезке. (Про существование дерева отрезков и прочих деревьев временно забудем.)

Если бы запросов обновления не было, мы бы решали эту задачу просто массивом префиксных сумм:

int s[maxn]; // [0, r)
s[0] = 0

for (int i = 0; i < n; i++)
    s[i+1] = s[i] + a[i];

Вернемся к исходной задаче. Разобьём все запросы изменения на блоки размера примерно $\sqrt q$, и будем честно каждые $\sqrt q$ запросов строить массив префиксных сумм за $O(n)$ с учетом всех предыдущих запросов.

Теперь для ответа на каждый запрос суммы мы можем потратить $O(1)$ времени на запрос к префиксным суммам для предыдущего чекпойнта плюс $O(\sqrt q)$ времени на «корректировку», просто линейно проходясь по всем ещё не учтенным запросам.

const int c = 300; // ~= sqrt(q)

struct query { int l, r, x; };
vector<query> buffer; // запросы, не учтенные в префиксных суммах

int sum(int l, int r) {
    int res = s[r + 1] - s[l];
    for (query q : buffer)
        // пересечем запрос суммы со всеми запросами
        res += q.x * max(0, min(r, q.r) - max(l, q.l));
    return res;
}

void rebuild() {
    vector<int> d(n, 0); // массив дельт

    for (query q : buffer) {
        d[q.l] += x;
        d[q.r + 1] -= x;
    }
    buffer.clear();

    int delta = 0, running_sum = 0;
    for (int i = 1; i <= n; i++) {
        p[i] += running_sum;
        delta += d[i];
        running_sum += delta;
    }
}

void upd(int l, int r, int x) {
    buffer.push_back({l, r, x});
    if (buffer.size() == c)
        // буфер слишком большой; надо пересчитать префиксные суммы и очистить его
        rebuild();
}

Такое решение будет работать за $O(n \sqrt q + q \sqrt q)$: каждые $\sqrt q$ запросов мы перестраиваем префиксные суммы за $O(n)$, и каждый запрос суммы мы просматриваем $O(\sqrt q)$ предыдущих.

#Превращение статических структур в динамические

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

Задача. Требуется добавлять точки в выпуклую оболочку и находить касательные (то есть находить точку, которая максимизирует скалярное произведение $a_i x + b_i y$).

Мы можем так же каждые $\sqrt n$ запросов перестраивать выпуклую оболочку, а при ответе на запрос касательной помимо кандидата из построенной выпуклой оболочки рассмотреть дополнительно $\sqrt n$ скалярных произведений из точек из буфера.

Это будет работать за $O(n \cdot (\sqrt n + \log n) + \sqrt n \cdot n) = O(n \sqrt n)$, если поддерживать отсортированный список точек, чтобы перестраивать оболочку за линейное время.

Задача. Требуется в заранее известном порядке добавлять и удалять точки из выпуклой оболочки и находить касательные.

Это уже немного сложнее. Разобьём запросы на блоки явно, и будем обрабатывать их по отдельности. На каждом блоке построим выпуклую оболочку только тех точек, которые существуют на всём её блоке, а остальные запросы сохраним в буфер — чтобы найти такие точки, нужно посмотреть на $O(\sqrt n)$ запросов наперед и отметить удаленные ребра в каком-нибудь массиве или хеш-таблице.

Тогда, при ответе на запрос касательной, помимо кандидата из построенной оболочки будем рассматривать все точки, которые существуют на момент данного запроса — найти все такие можно аналогично за $O(\sqrt n)$, проанализировав историю текущего блока.

#Структуры размера степеней двоек

Часто, если удалений в задаче нет или их можно как-то эмулировать, можно применить похожую, но более мощную технику: поддерживать $O(\log n)$ структур (например, выпуклых оболочек) размеров степеней двоек, причём так, что нет двух структур одинакового размера.

Для этого нужно при добавлении новой точки

• создать для неё новую структуру размера 1, где есть только одна новая точка;
• затем, если структура размера 1 уже существует, то объединить её с новой и создать структуру размера 2;
• затем, если структура размера 2 уже существует, то объединить её с новой и создать структуру размера 4

…и так далее, пока мы не найдем какую-то степень двойки, что структуры такого размера нет.

Общее число элементов $n$ однозначно задает, структуры какого размера будут в этом объединении: они будут соответствовать единицам в двоичной записи $n$, а значит, базовых структур всегда будет не более $O(\log n)$.

В случае с выпуклыми оболочками, каждую структуру мы можем строить за её размер, если мерджить отсортированные массивы точек. Структуры размера 1 будем строить каждую операцию; структуры размера 2 мы будем строить каждые 2 операции; структуры размера 4 — каждые 4 операции, и так далее. На поддержание такого объединения статических структур мы амортизировано потратим $O(n \log n)$ операций: по $O(n)$ для каждого размера.

На запрос же мы будем отвечать, передавая его во все $O(\log n)$ базовых структур и объединяя ответы. Для выпуклых оболочек это суммарно займет $O(\log^2 n)$ времени.

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