Декартово дерево по неявному ключу

«	Декартово дерево правит миром. За логарифм.	»
— Неизвестный автор

Основная идея

Возьмем структуру данных вектор. В её стандартной реализации мы умеем добавлять элемент в конец вектора, узнавать значение элемента, стоящего на определенной позиции, изменять элемент по номеру и удалять последний элемент. Предположим, что нам необходима структура данных с вышеуказанными свойствами, а также с операциями: добавить элемент в любое место (с соответствующим изменением нумерации элементов) и удалить любой элемент (также с соответствующим изменением нумерации). Такая структура существует и называется Декартово дерево по неявному ключу, или же rope (англ.веревка).

Пример описанного дерева с демонстрацией определения ключа $X$

Напомним, Декартово дерево — это структура данных, объединяющая в себе бинарное дерево поиска и бинарную кучу. При реализации же декартова дерева по неявному ключу попробуем слегка модифицировать эту структуру. А именно, оставим в нем только один ключ - ключ $Y$. Вместо второго ключа будем использовать следующую величину: количество элементов в нашей структуре, находящихся левее нашего элемента. Иначе говоря, будем считать ключом порядковый номер нашего элемента в дереве, уменьшенный на единицу.

Заметим, что при этом сохранится структура двоичного дерева поиска по этому ключу (то есть модифицированное декартово дерево так и останется декартовым деревом). Однако, с этим подходом появляется проблема: наши операции добавления и удаления элемента могут поменять нумерацию, и при наивной реализации на изменение всех ключей потребуется $O(n)$ времени, где $n$ — количество элементов в дереве.

Необходимо решить эту проблему. Основная идея заключается в том, что такой ключ $X$ сам по себе нигде не хранится. Вместо него будем хранить вспомогательную величину $C$: количество вершин в поддереве нашей вершины(в поддерево включается и сама вершину). Обратим внимание, что все операции с обычным декартовым деревом делались сверху. Также заметим, что если по пути до некой вершины просуммировать все такие величины в левых поддеревьях, в которые мы не пошли, увеличенные на единицу, то придя в саму вершину и добавив к этой величине количество элементов в её левом поддереве, мы получим как раз ее ключ $X$.

Операции, поддерживающие структуру декартова дерева

Структура обычного декартова дерева поддерживается с помощью двух операций: split — разбиение одного декартова дерева на два таких, что в одном ключ $X$ меньше, чем заданное значение, а в другом — больше, и merge — слияние двух деревьев, в одном из которых все ключи $X$ меньше, чем во втором. С учетом отличий декартова дерева по неявному ключу от обычного, операции теперь будут описываться так: разбиение дерева на два так, что в левом окажется ровно $t$ вершин, и слияние двух любых деревьев, соответственно.

Split

Пусть процедура split запущена в корне дерева с требованием отрезать от дерева $t$ вершин. Также известно, что в левом поддереве вершины находится $l$ вершин, а в правом $r$. Рассмотрим сначала два тривиальных случая. Первый: $l = t$. В этом случае процедура split должна просто пометить, что у корня больше нет левого сына, и вернуть его бывшего левого сына в качестве левого ответа, а сам корень — в качестве правого. Второй случай ($t = l + 1$) рассматривается аналогично. Следующий случай не так тривиален: $t \lt l$. В этом случае нужно рекурсивно запустить процедуру split от левого сына с тем же параметром $t$, и левая часть сына станет левым ответом нашей процедуры, а правая часть станет левым сыном корня, после чего корень станет правым ответом. Случай $t \gt l + 1$ рассматривается аналогично, с той лишь разницей, что от правого сына отрезается $t - l - 1$ вершин.

Merge

Посмотрим любую из реализаций процедуры merge. Заметим, что в ней программа ни разу не обращается к ключу $X$. Поэтому реализация процедуры merge для декартова дерева по неявному ключу вообще не будет отличаться от реализации той же процедуры в обычном декартовом дереве.

Поддержание корректности значений $C$

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

Применение описанного дерева

Таким образом, описана структура, от которой можно отрезать слева кусок произвольной длины и слить два любых куска в один в нужном порядке. Теперь мы имеем возможность:

• вставить элемент в любое место (отрежем нужное количество элементов слева, сольем левое дерево с деревом из одного добавленного элемента и результат — с правым деревом)
• переставить любой кусок массива куда угодно (сделаем нужные разрезы и слияния в правильном порядке)
• совершать групповые операции с элементами. Вспомним реализацию таких операций в дереве отрезков и поймем, что ничего не помешает нам сделать то же самое с описанным деревом. В групповые операции включается, естественно, и взятие функции от отрезка.
• сделав на одном исходном массиве два дерева из элементов разной четности, можно решить задачу про смену мест четных и нечетных на отрезке.

Ссылки

• Habrahabr - Декартово дерево по неявному ключу