1. Персистентные структуры данных (с прошлой пары)
1.1 Persistent Stack
1.2 Persistent Queue (5 стеков)
1.3 Persistent Deque (Pairing)
1.4 GC: reference counting
1.5 GC: стековый аллокатор и перестройка

2. Splay Tree
2.1 Add: как обычно, но повернём
2.2 Поворотики. Выражаем через одиночный поворот
2.3 Операция Splay (при наличии ссылок v->parent)
2.4 T(add) = Theta(T(splay))
2.5 Вес вершины, size_v, R(v), phi
2.6 Две леммы про Log
2.7 Амортизированное время splay. Случай zigzig.

3. Skip List
3.1 Обычный список: split, merge, insert, erase работают быстро, find долго
3.2 ссылки через 2^i
3.3 insert всё ломает. Вероятностное решение
3.4 Find. Erase. Add.

4. SQRT
4.1 Простая корневая: sqrt кусочков
4.2 split/merge
4.3 split/rebuild
4.4 [skip] отложенные операции, пример с countrange

5. [skip] Интерфейс Rope: insert(i, x), erase(i), get(i), split, merge
5.1 [skip] Реализации treap, AVL, RB, 2-3-tree, skip-list, splay, корневая

6. Splay Tree II
6.1 Задача о статически оптимальном BST; решение n^2
6.2 Static optimality theorem: Splay = O(sum k_i log(m/ki))
6.3 Splay = Theta(Static Opt)
6.4 Dynamic optimality conjecture