Общий подход к персистентности почти любой ссылочной структуры — это создавать копии всех вершин, в которых хоть что-то меняется, и менять это что-то в копиях, никогда не изменяя уже существующие вершины.
Персистентное дерево отрезков здесь не исключение. Просто будем при спуске создавать копию вершины перед тем, как что-либо менять в ней самой или её потомках. Асимптотика операций от этого не изменится, разве что общее потребление памяти увеличится до $O(m \log n)$.
Удобнее всего по аналогии с push в отложенных операциях определить функцию copy, копирующую детей текущей вершины, и просто без разбору вызывать её во всех вершинах, в которых что-то может измениться.
struct Segtree {
int lb, rb;
int s = 0;
Segtree *l = 0, *r = 0;
Segtree(int lb, int rb) : lb(lb), rb(rb) {
if (lb != rb) {
int t = (lb + rb) / 2;
l = new Segtree(lb, t);
r = new Segtree(t, rb);
}
}
void copy() {
if (l) {
l = new Segtree(*l);
r = new Segtree(*r);
}
}
void add(int k, int x) {
copy();
s += x;
if (l) {
if (k < l->rb)
l->add(k, x);
else
r->add(k, x);
}
}
int sum(int lq, int rq) {
// этот метод ничего не меняет -- он и так хороший
if (lq <= lb && rb <= rq)
return s;
if (max(lb, lq) >= min(rb, rq))
return 0;
return l->sum(lq, rq) + r->sum(lq, rq);
}
};
Теперь осталось только создать список версий, и после каждой операции копировать туда новый корень:
vector<Segtree*> roots;
roots.push_back(new Segtree(0, n));
void add(int k, int x, int v) {
Segtree *root = new Segtree(*roots[v]);
root->add(k, x);
roots.push_back(root);
}
В качестве альтернативного подхода можно копировать не детей, а текущую вершину, и возвращать её из рекурсии и переподвешивать за родителя. Это вычислительно эффективнее, но нужно сильно изменить реализацию.
#Применения
В контексте задач на структуры данных персистентное дерево отрезков особенно часто применяют в задачах, где применили бы метод сканирующей прямой, если бы запросы были известны заранее.
#Сумма на прямоугольнике
Задача. Даны $n$ точек на плоскости. Нужно в онлайн ответить на $q$ запросов числа точек на прямоугольнике.
Если бы можно было отвечать в оффлайн, мы бы разбили запрос на два запроса на префиксах и прошлись бы сканлайном слева направо, добавляя $y$-координаты точек в дерево отрезков и отвечая на запросы суммы на подотрезках — но так делать мы не можем.
Но точки в оффлайн известны. Добавим их в таком же порядке в персистентное дерево отрезков, а не обычное, и сохраним корни деревьев с разными $x$-координатами в порядке увеличения.
Теперь мы можем ответить на запрос, так же декомпозировав его на два и перенаправив их в две разные версии дерева отрезков, соответствующие большей и меньшей $x$-координатам. Таким образом, можно отвечать на запросы в онлайн за $O(q \log n)$ времени и памяти.
#Порядковые статистики
Задача. Дан отрезок из $n$ целых чисел и $q$ запросов $k$-той порядковой статистики на подотрезке.
Во-первых, сожмем все числа, чтобы они были от 1 до $n$.
Затем, пройдёмся с персистентным деревом отрезков для суммы по массиву слева направо, и когда будем обрабатывать элемент $a_k$, добавим единицу к $a_k$-ому элементу в дереве отрезков. Заметим, что сумма с $l$ по $r$ в таком дереве будет равна количеству элементов между $l$ и $r$ на текущем префиксе.
Дальше определим разность деревьев как дерево отрезков, которое получилось бы, если бы оно было построено поверх разности соответствующих массивов.
Что будет находиться в разности $r$-го и $l$-го дерева ($r > l$)? Там будут находиться количества вхождений чисел на отрезке массива с $l$ по $r$ — какой-то массив целых неотрицательных чисел. Если в таком разностном дереве сделать спуск, который находит последнюю позицию, у которой сумма на префиксе не превышает $k$ — она и будет ответом на запрос.
Если не обязательно строить разностное дерево явно, чтобы делать по нему спуск — можно просто спускаться одновременно в двух деревьях и везде вместо суммы $s$ использовать $(s_r - s_l)$:
int kth(Segtree *l, Segtree *r, int k) {
if (k == 0)
return l->lb;
int s = r->l->s - l->l->s;
if (s <= k)
return kth(l->l, r->l, k);
else
return kth(l->r, r->l, k - s);
}
Отметим, что эту и предыдущую задачу также можно решить через mergesort tree за $O(n \log^2 n)$, а также двумерными структурами за такую же асимптотику.
#Доминирующий элемент
Задача. Дан массив из $n$ элементов. Требуется ответить на $m$ запросов, есть ли на отрезке $[l, r)$ доминирующий элемент — тот, который встречается на нём хотя бы $\frac{r-l}{2}$ раз.
У этой задачи есть удивительно простое решение — взять около 100 случайных элементов для каждого проверить, является ли он доминирующим. Проверку можно выполнять за $O(\log n)$, посчитав для каждого значения отсортированный список позиций, на которых он встречается, и сделав в нём два бинпоиска. Вероятность ошибки в худшем случае равна $\frac{1}{2^{100}}$, и ей на практике можно пренебречь.
Но проверять 100 сэмплов — долго. Построим такое же дерево отрезков, как в прошлой задаче, и решим задачу «найти число, большее $\frac{n}{2}$ в массиве из $n$ неотрицательных целых чисел с суммой не более $n$» относительно разностного дерева. Это тоже будет спуском по нему: каждый раз идём в того сына, где сумма больше (потому что сын с меньшей суммой точно не доминирующий). Если в листе, куда мы пришли, значение больше нужного, возвращаем true, иначе false.
Упражнение. Придумайте, как модифицировать спуск в задаче где доминирующим считается элемент, встречающийся хотя бы $\frac{r-l}{k}$ раз для маленького $k$ (от 2 до 5).
#Как персистентный массив
С помощью дерева отрезков обычно и реализуют полностью персистентный массив — в общем случае быстрее $O(\log n)$ на запрос не получается. Персистентный массив в свою очередь можно использовать, чтобы делать персистентными не-ссылочные структуры — например, систему непересекающихся множеств.
В СНМ мы храним всё состояние в массивах, которые можно просто сделать персистентными через дерево отрезков. Асимптотика такой структуры будет $O(n \log n)$ времени и памяти — причем логарифм здесь и от самого СНМа (нужно пройтись по $O(\log n)$ предков — эвристику сжатия путей мы использовать не можем), так и от персистентного ДО (обновить значение какого-то $p_v$ и $s_v$ / $h_v$).