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

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

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

Ключ X

Как известно, декартово дерево — это структура данных, объединяющая в себе бинарное дерево поиска и бинарную кучу. При реализации же декартова дерева по неявному ключу модифицируем эту структуру. А именно, оставим в нем только приоритет [math]Y[/math] , а вместо ключа [math]X[/math] будем использовать следующую величину: количество элементов в нашей структуре, находящихся левее нашего элемента. Иначе говоря, будем считать ключом порядковый номер нашего элемента в дереве, уменьшенный на единицу.

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

Вспомогательная величина С

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

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

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

Split

Пусть процедура [math]\mathrm[/math] запущена в корне дерева с требованием отрезать от дерева [math]k[/math] вершин. Также известно, что в левом поддереве вершины находится [math]l[/math] вершин, а в правом [math]r[/math] . Рассмотрим все возможные случаи:

• [math]l \geqslant k[/math] . В этом случае нужно рекурсивно запустить процедуру [math]\mathrm[/math] от левого сына с тем же параметром [math]k[/math] . При этом новым левым сыном корня станет правая часть ответа рекурсивной процедуры, а правой частью ответа станет корень.
• [math]l \lt k[/math] Случай симметричен предыдущему. Рекурсивно запустим процедуру [math]\mathrm[/math] от правого сына с параметром [math]k — l — 1[/math] . При этом новым правым сыном корня станет левая часть ответа рекурсивной процедуры, а левой частью ответа станет корень.

 [math]\langle[/math]Treap, Treap[math]\rangle[/math] split(Treap t, int k) if t == [math] \varnothing [/math] return [math]\langle[/math][math] \varnothing [/math], [math] \varnothing [/math][math]\rangle[/math] int l = t.left.size if l [math]\small<\geqslant>[/math] k [math]\langle[/math]t1, t2[math]\rangle[/math] = split(t.left, k) t.left = t2 update(t) return [math]\langle[/math]t1, t[math]\rangle[/math] else [math]\langle[/math]t1, t2[math]\rangle[/math] = split(t.right, k - l - 1) t.right = t1 update(t) return [math]\langle[/math]t, t2[math]\rangle[/math] 

Merge

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

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

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

void update(Treap t) t.size = 1 + t.left.size + t.right.size

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

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

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

См. также

Источники информации

Источник

Неявный ключ

Обычное декартово дерево — это структура для множеств, каждый элемент которых имеет какой-то ключ. Эти ключи задают на этом множестве порядок, и все запросы к ДД обычно как-то привязаны к этому порядку.

Но что, если у нас есть запросы, которые этот порядок как-то нетривиально меняют? Например, если у нас есть массив, в котором нужно уметь

1. выводить сумму на произвольном отрезке,
2. «переворачивать» произвольный отрезок, то есть переставлять элементы с $l$ по $r$ в обратном порядке, не меняя остальные.

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

Решение такое: выкинем ключи, а вместо них будем поддерживать информацию, которая поможет неявно восстановить ключ, когда он нам будет нужен. А именно, будем хранить вместе с каждой вершиной размер её поддерева:

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

Размеры поддеревьев будем поддерживать по аналогии с суммой — напишем вспомогательную функцию, которую будем вызывать после каждого структурного изменения вершины.

Операция merge не меняется, так как нигде не использует ключи, а вот в split нужно использовать позицию корня вместо его ключа. Про split теперь удобнее думать как «вырежи первые k элементов»:

 Всё. Теперь у нас есть клёвая гибкая структура, которую можно резать как угодно, не опираясь на ключи.

#Пример: ctrl+x, ctrl+v

#Пример: переворот

Вернемся к изначальной задаче: нужно за $O(\log n)$ обрабатывать запросы переворота произвольных подстрок: значение $a_l$ поменять с $a_r$, $a_$ поменять с $a_$ и т. д.

Будем хранить в каждой вершине флаг rev , который будет означать, что её подотрезок перевернут:

 Поступим по аналогии с техникой отложенных операций в дереве отрезков — когда мы когда-либо встретим такую вершину, мы поменяем местами ссылки на её детей, а им самим передадим эту метку:

Аналогично, эту функцию будем вызывать в начале merge и split .

Саму функцию reverse реализуем так: вырезать нужный отрезок, поменять флаг.

Источник