$ Декартово дерево & Persistent tree
vb = [Ваня]
sk = [Сережа.K]
sm = [Сережа.М]
# $sk$ С/C++
## передача параметров (значение, ссылка, указатель, константа, указатель на указатель)
## пример использования указателя на указатель: нерекурсивный Split
## ошибки: string s, vector<int> a, global x += f() which changes x
# $sk$ Простейшее 2D-дерево (дерево отрезков сортированных массивов)
## Построение за O(nlogn) через merge
## Запрос за O(log^2n) деревом отрезков снизу и lower\_bound
# $sk$ Корневая, окончание
## Еще раз split & rebuild на примера вставки/удаления в середину массива
## Общая концепция: если что-то умеем делать для всего массива, то это же умеем делать на отрезке
# $sm$ Декартово дерево
## Явный ключ
### Определение: по X дерево поиска, по Y куча. Если Y случайные, получаем BST.
### Split, Merge
### Добавление, удаление, любая операция на отрезке через несколько Split и Merge
### Более быстрое добавление через 1 Split
### Корректность: пусть все X и Y различны, тогда существует единственное дерево → декартово дерево случайно
## Неявный ключ
### Пусть (x=i,y=random,z=a[i]). Посчитаем размер в каждой вершине. Заметим, что x можно не хранить, поменяем if в split.
### Вставка в середину массива за O(logn), удаление.
### Поменять куски массива местами
### Reverse отрезка
## RBST: y можно не хранить, а в merge вместо сравнения Y-ков генерировать рандом
# $sm$ Персистентность
## Персистентное дерево отрезков
## Персистентное декартово дерево
## Персистентный массив с операциями за O(logn)
## Весь мир − массивы и деревья. Значит, весь мир можно сделать персистентным за не более чем лишний логарифм!
# $sm$ 2D деревья
## 2D запрос на массиве: дерево отрезков сортированных массивов
## 2D запрос на меняющемся массиве: дерево отрезков декартовых деревьев