Так же, как и с деревом отрезков, персистентной версией декартова дерева можно решать интересные задачи — особенно часто связанные со строками. Разберем сначала несколько примеров, а потом перейдем к реализации.
#Примеры задач
Задача. Дана строка. Требуется выполнять в ней копирования, удаления и вставки в произвольные позиции.
Построим персистентное ДД поверх символов. Тогда просто вызвав два 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$?