Персистентное дерево отрезков

Основной инструмент темы. Узлы лежат в массивах, версия задаётся номером корня, изменение создаёт $O(\log n)$ новых узлов.

Устройство

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

std::vector<int> leftKid, rightKid, count;
int used = 1;                       // узел 0 — общий пустой

int insertAt(int previous, int low, int high, int pos) {
    int node = used++;
    leftKid[node] = leftKid[previous];
    rightKid[node] = rightKid[previous];
    count[node] = count[previous] + 1;
    if (low == high) return node;
    int middle = (low + high) / 2;
    if (pos <= middle) leftKid[node] = insertAt(leftKid[previous], low, middle, pos);
    else rightKid[node] = insertAt(rightKid[previous], middle + 1, high, pos);
    return node;
}

Запрос читает версию как обычное дерево отрезков, начиная с её корня:

int countIn(int node, int low, int high, int from, int to) {
    if (!node || to < low || high < from) return 0;
    if (from <= low && high <= to) return count[node];
    int middle = (low + high) / 2;
    return countIn(leftKid[node], low, middle, from, to)
         + countIn(rightKid[node], middle + 1, high, from, to);
}

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

Сколько узлов заказывать

Память считают заранее: выделять по узлу на ходу в разы медленнее.

$$\text{узлов} \approx (\text{число изменений}) \cdot (\lceil \log_2 n \rceil + 2).$$

Для $n = q = 2 \cdot 10^5$ это около $4 \cdot 10^6$ узлов, то есть 48 мегабайт на три массива int. Если изменений на элемент два (как в задаче о количестве различных), множитель удваивается. Постройка начального дерева добавляет ещё $2n$ узлов.

Половина падений в этой теме — не неверный ответ, а выход за границы массива узлов.

Префикс как версия

Приём, ради которого всё затевается. Дерево строится по значениям (после сжатия координат), версия создаётся на каждый префикс: версия $i$ содержит первые $i$ элементов массива.

for (int i = 0; i < n; i++) roots[i + 1] = insertAt(roots[i], 0, size - 1, at[i]);

Тогда отрезок — это разность двух версий:

$$\text{count}_{[l, r]}(v) = \text{count}_{r}(v) - \text{count}_{l - 1}(v).$$

Разность нигде не хранится: она считается на ходу, во время одного спуска по обеим версиям сразу.

K-я порядковая статистика на отрезке

Главное применение. Спускаемся по двум версиям одновременно; в левое поддерево уходим, если в нём хватает элементов.

int kthBetween(int was, int now, int low, int high, int k) {
    while (low < high) {
        int middle = (low + high) / 2;
        int inLeft = count[leftKid[now]] - count[leftKid[was]];
        if (k <= inLeft) { was = leftKid[was]; now = leftKid[now]; high = middle; }
        else { k -= inLeft; was = rightKid[was]; now = rightKid[now]; low = middle + 1; }
    }
    return low;                     // номер значения в сжатом списке
}

Одна из немногих задач, у которой без персистентности нет простого решения: обычные способы дают $O(\log^2 n)$ или требуют офлайна.

Что кладут в лист

Код один и тот же; задача — понять, что должно лежать в листе и по какой оси строится дерево.

задача	ось дерева	в листе	запрос
сколько $\le x$ среди первых $i$	значения	количество	сумма по префиксу
точки в прямоугольнике	значения	количество	разность двух версий
$k$-я на отрезке	значения	количество	спуск по разности
сколько различных на $[l, r]$	позиции	количество	сумма в версии $r$
mex отрезка	значения	последнее вхождение	спуск по минимуму
$k$-я на пути до корня	значения	количество	версия = вершина дерева

Две строки стоит разобрать отдельно.

Различные на отрезке. Дерево строится по позициям, а не по значениям. Добавляя элемент на позицию $i$, кладём $+1$ в позицию $i$ и $-1$ в позицию предыдущего вхождения того же значения. Тогда в версии $r$ единицы стоят ровно в последних вхождениях, и ответ — сумма на $[l, r]$.

Mex отрезка. В листе значения $v$ хранится номер его последнего вхождения на префиксе, во внутренних узлах — минимум. Значение отсутствует на $[l, r]$ ровно тогда, когда в версии $r$ его лист меньше $l$; mex — самый левый такой лист, то есть обычный спуск с предпочтением левого сына.

Версия — не обязательно префикс

Версии не обязаны образовывать цепочку. Если дерево из условия подвешено за вершину $1$, можно завести версию на каждую вершину:

$$\text{root}[v] = \text{insert}(\text{root}[\text{parent}(v)],\ w_v).$$

Версия вершины содержит ровно числа на пути от неё до корня — и $k$-я статистика на пути ищется тем же спуском. Отсюда же берутся решения задач вида «$k$-я на пути между двумя вершинами»: там складывают и вычитают четыре версии, включая наименьшего общего предка.

Когда персистентность не нужна

Почти у каждой задачи этого списка есть офлайн-решение: отсортировать запросы по правой границе и вести обычное дерево Фенвика. Оно проще, короче и быстрее.

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

Полезная привычка: писать офлайн-решение как проверку персистентного. Оно пишется за десять минут и ловит почти все ошибки на случайных тестах.

Частые ошибки

ошибка	как проявляется
мало узлов	падение или мусор в ответах на больших тестах
запись в узел 0	врут сразу все версии, обычно не с первого запроса
нейтральный элемент 0 для максимума	неверно только на полностью отрицательных данных
roots[l] вместо roots[l - 1]	ответ меньше на единицу, и только когда $a_l$ подходит
граница «строго меньше» вместо «не больше»	расхождение лишь на значениях, которые есть в массиве

Смежное: персистентные структуры, дерево отрезков, дерево Фенвика, сжатие координат.