Персистентное декартово дерево

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

#Примеры задач

Задача. Дана строка. Требуется выполнять в ней копирования, удаления и вставки в произвольные позиции.

Построим персистентное ДД поверх символов. Тогда просто вызвав два split-а, мы можем получить копию любой подстроки (указатель вершину), которую потом можно вставлять куда угодно, при этом оригинальную подстроку мы не изменим.

Задача. Дана строка. Требуется выполнять в ней копирования, удаления, вставки в произвольные позиции и сравнение произвольных подстрок.

Можно в вершинах хранить полиномиальный хеш соответствующей подстроки. Тогда мы можем проверять равенство подстрок сравниванием хешей вершин, полученных теми же двумя сплитами.

Чтобы сравнивать стоки на больше-меньше, а не только на равенство, можно стандартный трюк с бинарным поиском: перебрать длину совпадающего суффикса, и, когда она найдется, посмотреть на следующий символ.

Задача. Дана — не поверите — строка. Требуется выполнять в ней такие же операции изменения и после каждого запроса находить минимальный период строки, то есть такое минимальное число $k$ , что из префикса длины $k$ повторением $\frac{n}{k}$ раз получается вся строка.

Научимся сначала с помощью построенного дерева проверять, что $k$ является периодом (каким-нибудь, не обязательно минимальным). Выделим первые $k$ символов и посчитаем от них полиномиальный хеш $h_k$ , а также хеш $h$ от всей строки. Если вся строка — это просто $\frac{n}{k}$ записанных вместе копий префикса $k$ , то хеш от неё должен быть равен:

h = h_k + h_k \cdot p^k + h_k \cdot p^{2k} + \ldots + h_k \cdot p^{n-k}

Соответственно, мы можем выполнять проверку за $O(\log n)$ , посчитав выделением или спуском хеш от префикса длины $k$ .

Теперь мы можем перебрать разные кандидаты $k$ среди делителей $n$ и каждый за логарифм проверить. Можно и ещё быстрее, если заметить, что если $p$ является делителем какого-то периода, то $\frac{n}{p}$ тоже будет периодом. Можно посмотреть на разложение $n$ и такой проверкой убирать по одному простому множителю за раз, пока не останется только факторизация минимального периода.

Так как у числа $n$ не более $O(\log n)$ множителей в факторизации, то решение будет работать за $O(\log^2 n)$ на запрос (не считая факторизации — но если есть разумное ограничение на длину строки, то её можно предпосчитать).

#Реализация

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

Node* copy(Node *v) { return new Node(*v); }

Во всех методах мы будем начинать с копирования всех упоминаемых в ней вершин. Например, персистентный split начнётся так:

Pair split(Node *p, int x) {
    p = copy(p);
    // ...
}

В дереве отрезков просто создавать копии вершин было достаточно — этого обычно достаточно для всех детерминированных структур данных, но с декартовым деревом всё сложнее.

Существует тест, который «валит» приоритеты: можно раскопировать много версий одной вершины, а все остальные — удалить. Тогда у всех вершин будет один и тот же приоритет, и дерево превратится в «бамбук», в котором все операции будут работать за $O(n)$ .

У этой проблемы есть очень элегантное решение — избавиться от приоритетов и делать следующее переподвешивание: если размер левого дерева равен $L$ , а размер правого $R$ , то будем подвешивать за левое с вероятностью $\frac{L}{L+R}$ , иначе за правое.

Теорема. Такое переподвешивание эквивалентно приоритетам.

Доказательство. Покажем, что все вершины всё так же имеют равную вероятность быть корнем. Докажем по индукции:

Лист имеет вероятность 1 быть корнем себя (база индукции)
Переход индукции — операция merge. Любая вершина левого дерева была корнем с вероятностью $\frac{1}{L}$ (по предположению индукции), а после слияния она будет корнем всего дерева с вероятностью $\frac{1}{L} \cdot \frac{L}{L+R} = \frac{1}{L+R}$ . С вершинами правого дерева аналогично.

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

Node* merge(Node *l, Node *r) {
    if (!l) return r;
    if (!r) return l;
    l = copy(l), r = copy(r);
    if (rand() % (size(l) + size(r)) < size(l)) {
        // ...
    }
    else {
        // ...
    }
}

Философский вопрос: можно ли декартово дерево называть декартовым, если из него удалить и $x$ , и $y$ ?