Неявный ключ

Если ключ в узле не хранить, а вычислять как позицию, декартово дерево превращается из множества в массив. Причём в такой массив, у которого меняются и длина, и порядок.

Позиция как размер

Позиция элемента — это количество элементов левее него. Она равна размеру левого поддерева плюс позиция родителя, и нигде не хранится: спуск считает её на лету.

Разрез идёт не по ключу, а по количеству:

void split(int node, int count, int &first, int &second) {   // первые count — в first
    if (!node) { first = second = 0; return; }
    push(node);
    if (size[left[node]] >= count) { split(left[node], count, first, left[node]); second = node; }
    else { split(right[node], count - size[left[node]] - 1, right[node], second); first = node; }
    pull(node);
}

Единица в count - size[left] - 1 — сам узел: он тоже уходит в левую часть. Ошибка здесь сдвигает весь массив, и видна она на первом же маленьком тесте — если такой тест есть.

Что становится возможным

операция	как	стоимость
вставить в позицию $p$	разрез по $p-1$, две склейки	$O(\log n)$
удалить позицию $p$	два разреза, склейка	$O(\log n)$
сумма или минимум на $[l, r]$	вырезать кусок, посмотреть корень	$O(\log n)$
перенести отрезок в другое место	три разреза, склейка в другом порядке	$O(\log n)$
поменять два отрезка местами	четыре разреза	$O(\log n)$
циклический сдвиг отрезка	разрез отрезка надвое, склейка наоборот	$O(\log n)$

Стоимость не зависит от длины переносимого куска. Элементы не двигаются — двигаются ссылки. Массивом перенос половины стоил бы $O(n)$, и на ста тысячах операций это десять миллиардов перемещений.

Построение за линию

Собирать дерево из массива по одному элементу — $n$ склеек, то есть $O(n \log n)$. Быстрее строить сразу: элементы уже идут по возрастанию позиции, поэтому годится обычный приём с монотонным стеком.

for (Long value : values) {
    int node = makeNode(value), last = 0;
    while (!stack.empty() && priority[stack.back()] < priority[node]) { last = stack.back(); stack.pop_back(); pull(last); }
    left[node] = last;
    pull(node);
    if (!stack.empty()) right[stack.back()] = node; else root = node;
    stack.push_back(node);
}

Разрез по ключу и разрез по количеству

Это разные функции, и обе законны для одного и того же дерева. Выбор зависит от вопроса:

• «все элементы меньше $x$» — разрез по ключу;
• «первые $k$ элементов» — разрез по количеству.

В дереве по ключу иногда нужен второй: например, чтобы сложить $k$ наименьших.

Что спрашивать нельзя даром

При перевороте отрезка бесплатны только величины, не зависящие от порядка: сумма, минимум, количество, набор значений. «Первый элемент отрезка» или «сумма с чередующимися знаками» потребуют хранить в узле обе версии — прямую и перевёрнутую.

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