Декартово дерево

Дерево отрезков работает с массивом фиксированной длины. Как только элементы надо вставлять и удалять, а не только менять, нужна другая структура.

Декартово дерево хранит в узле две величины: ключ и приоритет. По ключам это дерево поиска: левое поддерево меньше, правое больше. По приоритетам это куча: родитель больше детей.

Пара условий определяет форму дерева однозначно. А если приоритеты выбраны случайно, форма совпадает с формой случайного дерева поиска — значит ожидаемая глубина $O(\log n)$, и никакой явной балансировки не нужно.

Название — от точек $(\text{ключ}, \text{приоритет})$ на плоскости. По-английски treap: tree + heap.

Split и merge

Всё держится на двух операциях.

операция	что делает	условие
split(t, x)	режет на «ключи меньше $x$» и «остальные»	нет
merge(a, b)	склеивает два дерева	все ключи $a$ меньше всех ключей $b$

void split(int node, Long bound, int &first, int &second) {
    if (!node) { first = second = 0; return; }
    if (key[node] < bound) { split(right[node], bound, right[node], second); first = node; }
    else { split(left[node], bound, first, left[node]); second = node; }
    pull(node);
}

int merge(int a, int b) {
    if (!a || !b) return a ? a : b;
    if (priority[a] > priority[b]) { right[a] = merge(right[a], b); pull(a); return a; }
    left[b] = merge(a, left[b]); pull(b); return b;
}

Обе рекурсии идут по одному пути от корня вниз, поэтому обе стоят $O(\log n)$.

Что собирается из них

задача	как
вставить ключ	разрезать по нему и склеить три части
удалить ключ	вырезать отрезок $[x, x]$ и выбросить
удалить все ключи из $[l, r]$	два разреза, одна склейка — за логарифм, сколько бы их ни было
сумма ключей из $[l, r]$	вырезать кусок и посмотреть сумму в его корне
$k$-й по возрастанию	спуск по размерам поддеревьев
количество ключей меньше $x$	спуск, складывающий размеры левых поддеревьев

Последние две строки — то, чего нет у std::set: там до $k$-го элемента приходится идти шагами.

Что хранить в узле

Правило простое: то, что нельзя получить спуском за тот же логарифм.

• размер поддерева — хранить (нужен для статистик);
• сумму, минимум, НОД, маску значений — хранить, если их спрашивают;
• максимум по всему дереву — не хранить: это просто самый правый узел.

Пересчёт всегда один и тот же:

void pull(int node) {
    size[node] = 1 + size[left[node]] + size[right[node]];
    sum[node] = key[node] + sum[left[node]] + sum[right[node]];
}

Четыре ошибки, которые делают все

pull не на выходе. Дети меняются до возврата из рекурсии, значит пересчитывать надо после. Забыть — получить дерево, которое работает, но врёт в размерах и суммах.

Нет нулевого узла. Заведите узел номер 0 с нулевыми размером и суммой: тогда в pull не нужно проверок на пустоту, и забыть проверку негде.

Дерево не собрано обратно. Разрез портит структуру; забытый merge после запроса теряет часть множества, и ошибка проявляется далеко от места, где сделана.

Плохой генератор приоритетов. rand() на части систем даёт 15 бит; совпадений хватит, чтобы дерево выродилось в список. Берите mt19937.

Стоимость

операция	ожидание	худший случай
split, merge, вставка, удаление, поиск	$O(\log n)$	$O(n)$
построение из отсортированной последовательности	$O(n)$	$O(n)$

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

Смежное: неявный ключ, отложенные операции, дерево отрезков.