Сбалансированные деревья (3 мая 2017)

1. Интерфейс Rope: insert(i, x), erase(i), get(i), split, merge, rotatel
1. Возможные быстрые реализации: treap, AVL, RB, 2-3, skip-list, splay, корневая
2. Skip-list
1. List: умеет делать Add и Del за O(1), если уже известно место; сложности с Find.
2. Добавим несколько уровней: ссылки вперёд на 2, на 4, на 8 и т.д.
3. Если мы вставим 1 элемент всё передвинется... поэтому будем хитрее: каждый элемент есть на уровне выше с вероятностью 1/2
4. Не забыть: (а) фиктивный элемент, общий для всех списков; (б) мы не храним индексы, храним только длины рёбер
3. Splay-tree
1. Собственно дерево: add и del, splay = zig-zig + zig-zag + last one.
2. Вращения: zig-zag = double = 2 signle, zig-zig = 2 single в другом порядке.
3. Теорема об амортизированном времени работы. Потенциал = ∑ log(S_v) (S_v − размер поддерева)
4. Finger-теорема: ∑ t_i = O(∑ k_i log(n/k_i)) ≤ O(n log n).

1. SQRT-decomposition
1. Версия с sqrt(n) кусками массива и минимум на отрезке.
2. Что делать, если нужно вставлять и удалять элементы? Два решения: split/merge; rebuild.
3. Версия только со split и rebuild.
4. Отложенные операции: сортированный массив + добавление новых элементов + число элементов от x до y. Концепция: есть казалось бы неизменяемая структура.. сделаем её изменяемой.
2. Persistent
1. Peristent Array: "Дерево отрезков" vs RBST
2. Offline
3. Persistent Queue/Deque
3. Статическая оптимальность
1. Формулировка задачи с вероятностями и матожиданием
2. Решение Кнутом за O(n²)

1. Chinese tree: деревья, которые следят за "размер внука не более половины меня"
2. Динамическая оптимальность. Гипотеза: splay tree is dynamic optimal.