Форум программистов [Powered by Invision Power Board]

Код

Неявные декартовы деревья

Неявное декартово дерево - это простая модификация обычного декартового дерева, которая, тем не менее, оказывается очень
мощной структурой данных. Фактически, неявное декартово дерево можно воспринимать как массив, над которым можно 
реализовать следующие операции (все за O (log N) в режиме онлайн):

    * Вставка элемента в массив в любую позицию
    * Удаление произвольного элемента
    * Сумма, минимум/максимум на произвольном отрезке, и т.д.
    * Прибавление, покраска на отрезке
    * Переворот (перестановка элементов в обратном порядке) на отрезке

Ключевая идея заключается в том, что в качестве ключей key следует использовать индексы элементов в массиве. Однако явно 
хранить эти значения key мы не будем (иначе, например, при вставке элемента пришлось бы изменять key в O (N) вершинах дерева).

Заметим, что фактически в данном случае ключ для какой-то вершины - это количество вершин, меньших неё. Следует заметить, 
что вершины, меньшие данной, находятся не только в её левом поддереве, но и, возможно, в левых поддеревьях её предков. Более 
строго, неявный ключ для некоторой вершины t равен количеству вершин cnt(t->l) в левом поддереве этой вершины плюс 
аналогичные величины cnt(p->l)+1 для каждого предка p этой вершины, при условии, что t находится в правом поддереве для p.

Ясно, как теперь быстро вычислять для текущей вершины её неявный ключ. Поскольку во всех операциях мы приходим в 
какую-либо вершину, спускаясь по дереву, мы можем просто накапливать эту сумму, передавая её функции. Если мы идём в левое 
поддерево - накапливаемая сумма не меняется, а если идём в правое - увеличивается на cnt(t->l)+1.