Изменения

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

Напомним, '''[[Декартово дерево]]''' {{---}} это структура данных, объединяющая в себе бинарное дерево поиска и бинарную кучу. Для решения задачи, поставленной в предыдущей главе, попробуем слегка модифицировать эту структуру. Если конкретнее, то оставим в нем только один ключ - ключ <tex>Y</tex>. Вместо второго ключа будем использовать следующую величину: '''количество элементов в нашей структуре, находящихся левее нашего элемента'''. Если проще, то будем считать ключом порядковый номер нашего элемента в дереве, уменьшенный на единицу.

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

Структура обычного декартова дерева поддерживается с помощью двух операций: '''split''' {{---}} разбиение одного декартова дерева на два таких, что в одном ключ <tex>X</tex> меньше, чем заданное значение, а в другом {{---}} больше, и '''merge''' {{---}} слияние двух деревьев, в одном из которых все ключи <tex>X</tex> меньше, чем во втором. С учетом отличий декартова дерева по неявному ключу от обычного, операции теперь будут описываться так: разбиение дерева на два так, что в левом окажется ровно <tex>t</tex> вершин, и слияние двух любых деревьев.

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

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

===Поддержание корректности ключей значений <tex>XС</tex>===Единственное действие, обеспечивающее корректность этих ключей значений заключается в том, что после любого действия с детьми вершины нужно записать в ее ключ поле <tex>XС</tex> сумму этих ключей полей в ее новых детях, увеличенную на единицу.

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