Дерево слияний и порядковые статистики

Пока в узле лежало одно число, дерево отвечало на вопросы про сумму и максимум. Теперь положим в узел отсортированный массив всех элементов его отрезка.

Строится это снизу вверх слиянием, как в сортировке слиянием, за $O(n \log n)$. Столько же занимает память: каждый элемент лежит на всех $\log n$ уровнях по одному разу.

void build(int v, int tl, int tr) {
    if (tl == tr) { tree[v] = {a[tl]}; return; }
    int tm = (tl + tr) / 2;
    build(2 * v, tl, tm);
    build(2 * v + 1, tm + 1, tr);
    tree[v].resize(tr - tl + 1);
    std::merge(tree[2 * v].begin(), tree[2 * v].end(),
               tree[2 * v + 1].begin(), tree[2 * v + 1].end(), tree[v].begin());
}

Сколько чисел меньше x

Запрос разбивается на $O(\log n)$ узлов, и в каждом ответ находится двоичным поиском по отсортированному массиву. Итого $O(\log^2 n)$ на запрос.

int count = std::lower_bound(tree[v].begin(), tree[v].end(), x) - tree[v].begin();

Логарифм в квадрате при $n = q = 10^5$ — это около $3 \cdot 10^7$ обращений, что проходит. Но константа у двоичного поиска по чужой памяти большая, и на $10^6$ такое решение уже не годится.

Главный минус — массивы неизменяемы. Вставить элемент в отсортированный массив узла нельзя, не сдвинув половину. Дерево слияний живёт в задачах без изменений.

K-е по величине на отрезке

Первый способ — двоичный поиск по ответу поверх запроса «сколько меньше $x$». Получается $O(\log^3 n)$, и это заметно медленно.

Второй способ — дерево с сохранением версий (персистентное). Идея простая: добавляя $i$-й элемент в дерево по значениям, мы меняем только путь от корня к листу — это $\log n$ узлов. Остальные можно не копировать, а переиспользовать.

$$\text{версия } i \;=\; \text{версия } i - 1 \;+\; O(\log n) \text{ новых узлов}.$$

Тогда «какие числа лежат в $[l, r]$» — это разность версий $r$ и $l-1$: количество в любом узле считается вычитанием счётчиков двух версий. Спуск с этой разностью даёт $k$-ю статистику за один $O(\log n)$.

int kth(int leftVersion, int rightVersion, int tl, int tr, int k) {
    if (tl == tr) return tl;
    int inLeft = count[left[rightVersion]] - count[left[leftVersion]];
    int tm = (tl + tr) / 2;
    if (k <= inLeft) return kth(left[leftVersion], left[rightVersion], tl, tm, k);
    return kth(right[leftVersion], right[rightVersion], tm + 1, tr, k - inLeft);
}

Узлов всего $O(n \log n)$, и хранятся они не в куче массивов, а в трёх плоских: left, right, count. Индексы вместо указателей здесь не оптимизация, а способ не утонуть в аллокациях.

Разность версий работает потому, что счётчик — величина обратимая. Для максимума такой фокус не пройдёт, и запрос про максимум на отрезке версий персистентным деревом не решается.

Что выбирать

• запросов немного, изменений нет — дерево слияний, оно пишется вдвое короче;
• запросов много или нужна именно $k$-я статистика — персистентное дерево;
• изменения есть — ни то, ни другое; смотрите в сторону корневой декомпозиции или разбиения запросов на офлайн-группы.