61
правка
Изменения
Нет описания правки
==Основная идея==
Возьмем структуру данных [[Саморасширяющийся массив|вектор]]. В её стандартной реализации мы умеем добавлять элемент в конец вектора, узнавать значение элемента, стоящего на определенной позиции, изменять элемент по номеру и удалять последний элемент. Предположим, что нам необходима структура данных с вышеуказанными свойствами, а также с операциями: добавить элемент в любое место (с соответствующим изменением нумерации элементов) и удалить любой элемент (также с соответствующим изменением нумерации). Такая структура существует и называется ''декартово дерево по неявному ключу''.
Как известно, [[декартово дерево]] {{---}} это структура данных, объединяющая в себе бинарное дерево поиска и бинарную кучу. При реализации же декартова дерева по неявному ключу модифицируем эту структуру. А именно, оставим в нем только приоритет <tex>Y</tex>, а вместо ключа <tex>X</tex> будем использовать следующую величину: '''количество элементов в нашей структуре, находящихся левее нашего элемента'''. Иначе говоря, будем считать ключом порядковый номер нашего элемента в дереве, уменьшенный на единицу.
Заметим, что при этом сохранится структура [[Дерево_поиска,_наивная_реализация|двоичного дерева поиска]] по этому ключу (то есть модифицированное декартово дерево так и останется декартовым деревом). Однако, с этим подходом появляется проблема: операции добавления и удаления элемента могут поменять нумерацию, и при наивной реализации на изменение всех ключей потребуется <tex>O(n)</tex> времени, где <tex>n</tex> {{---}} количество элементов в дереве.
===Вспомогательная величина С===
Решается эта проблема довольно просто. Основная идея заключается в том, что такой ключ <tex>X</tex> сам по себе нигде не хранится. Вместо него будем хранить вспомогательную величину <tex>C</tex>: '''количество вершин в поддереве нашей вершины''' (в поддерево включается и сама вершина). Обратим внимание, что все операции с обычным декартовым деревом делались сверху. Также заметим, что если по пути до некой вершины просуммировать все такие величины в левых поддеревьях, в которые мы не пошли, увеличенные на единицу, то придя в саму вершину и добавив к этой величине количество элементов в её левом поддереве, мы получим как раз ее ключ <tex>X</tex>.
[[Файл:DDpoNK.png|Пример описанного дерева с демонстрацией определения ключа <tex>X</tex>]]
==Операции, поддерживающие структуру декартова дерева==
===Split===
Пусть процедура <tex>splitSplit</tex> запущена в корне дерева с требованием отрезать от дерева <tex>t</tex> вершин. Также известно, что в левом поддереве вершины находится <tex>l</tex> вершин, а в правом <tex>r</tex>. Рассмотрим все возможные случаи: * <tex>l = t</tex>. В этом случае процедура <tex>splitSplit</tex> должна просто пометить, что у корня больше нет левого сына, и вернуть его бывшего левого сына в качестве левой части ответа, а сам корень {{---}} в качестве правой.
* Случай (<tex>t = l + 1</tex>) рассматривается аналогично предыдущему.
* <tex>t < l</tex>. В этом случае нужно рекурсивно запустить процедуру <tex>splitSplit</tex> от левого сына с тем же параметром <tex>t</tex>, и левая часть сына станет левой частью ответа нашей процедуры, а правая часть сына станет левым сыном корня, после чего корень станет правой частью ответа.
* Случай <tex>t > l + 1</tex> рассматривается аналогично предыдущему, с той лишь разницей, что от правого сына отрезается <tex>t - l - 1</tex> вершин.
===Merge===
Посмотрим любую из [[Декартово дерево#Операция merge|реализаций]] процедуры <tex>mergeMerge</tex>. Заметим, что в ней программа ни разу не обращается к ключу <tex>X</tex>. Поэтому реализация процедуры <tex>mergeMerge</tex> для декартова дерева по неявному ключу вообще не будет отличаться от реализации той же процедуры в обычном декартовом дереве.
===Поддержание корректности значений C===
==Применение описанного дерева==
Таким образом, описана структура, от которой можно отрезать слева кусок часть произвольной длины и слить два любых куска две любые части в один одну в нужном порядке. Теперь мы имеем возможность:
* вставить элемент в любое место (отрежем нужное количество элементов слева, сольем левое дерево с деревом из одного добавленного элемента и результат {{---}} с правым деревом);
* переставить любой кусок массива куда угодно (сделаем нужные разрезы и слияния в правильном порядке);
