Persistent segment tree: идея и применение для k-й порядковой статистики на отрезке?
Классическая задача: дан массив, много запросов «k-й по величине элемент на подотрезке [l, r]». Говорят, это решается персистентным деревом отрезков. Не понимаю, что значит «персистентное» и как это даёт ответ на отрезке. Объясните идею и оценку.
2 ответа
Персистентное (persistent) дерево отрезков хранит все версии структуры после каждого обновления, не копируя её целиком. При обновлении создаётся только O(log n) новых узлов вдоль пути от корня к листу, остальные переиспользуются из старой версии (узлы неизменяемы, ссылки общие). Каждая версия — свой корень.
Для k-й статистики на отрезке: сжимаем значения, строим дерево отрезков по значениям (в узле — сколько чисел из диапазона значений попало). Версия i = дерево, в которое добавлены первые i элементов массива. Тогда «частоты значений на [l, r]» = версия r минус версия l-1 поузловой разностью. Спускаемся по этой разности как в k-й единице:
int kth(int rootL, int rootR, int tl, int tr, int k) {
if (tl == tr) return tl;
int tm = (tl + tr) / 2;
int leftCnt = cnt[L[rootR]] - cnt[L[rootL]]; // чисел значения <= tm на [l,r]
if (leftCnt >= k) return kth(L[rootL], L[rootR], tl, tm, k);
return kth(R[rootL], R[rootR], tm+1, tr, k - leftCnt);
}
Сложность: построение всех версий O(n log n) по времени и памяти, каждый запрос O(log n). Это стандартное решение задачи о k-й порядковой статистике на отрезке без оффлайна и без MO.
Грабли persistent: память. Каждое обновление добавляет ~log2(n) узлов, поэтому пул узлов — порядка n * (log n + константа). Закладывайте массив на n * 20 узлов с запасом, иначе RE. Не аллоцируйте узлы через new в цикле — держите заранее выделенный пул и счётчик:
struct Vertex { int l, r, cnt; } tr[N * 20];
int cur = 0;
int newLeaf(int x) { tr[++cur] = {0,0,x}; return cur; }
Ещё нюанс: узлы неизменяемы, поэтому никогда не пишите в уже созданный узел — при update всегда создавайте копию и меняете только её. Если случайно мутируете общий узел, испортите все версии, которые на него ссылаются → трудноуловимый WA. Применения шире k-й статистики: версии массива во времени, «откат» состояния, persistent DSU и т.п.