Иногда чтобы решить задачу полной персистентности от структуры не нужно, но нужно уметь хоть как-то откатываться до более ранних состояний.
В этой статье мы рассмотрим несколько общих подходов и их популярные применения.
#Корневая эвристика по запросам
Рассмотрим стандартную задачу: есть массив размера $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)$ времени.
Помимо выпуклых оболочек и огибающих, такой подход полезен, например, для обновления строковых автоматов и для динамического построения индекса для поиска.