Декартово дерево & Persistent tree

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