Изменения

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

Заметим, что при этом сохранится структура [[Дерево_поиска,_наивная_реализация|двоичного дерева поиска]] по этому ключу(т.е. наше то есть модифицированное декартово дерево так и останется декартовым деревом). Однако, с этим подходом появляется проблема: наши операции добавления и удаления элемента могут поменять нумерацию, и при наивной реализации на изменение всех ключей потребуется <tex>O(n)</tex> времени, где <tex>n</tex> {{---}} количество элементов в дереве.

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

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

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

* сделав на одном исходном массиве два дерева из элементов разной четности, можно решить задачу про смену мест четных и нечетных на отрезке (одно из домашних заданий)* повелевать миром.