## ЛКШ 2018, 3-й день, Больше структур данных Богу структур данных (Сергей Копелиович)

1. Persistent: сборка мусора

1. Задача: копирование памяти
2. Варианты сборки: стек, список

2. ETT = Euler-Tour-Tree (Acyclic Dynamic Connectivity Online)

1. Подробно про реализацию, так как будет задача в контесте

3. Link-Cut-Tree

1. Expose, потенциал, logn вызовов split/merge
2. MakeRoot, Link, Cut функция на пути

4. Splay деревья

1. Операция Splay, выражение через неё Split, Merge, Add, Del
2. [skipped] Доказательство времени работы 3(log R(v) - log R(u)) + 1
3. [skipped] Доказательство времени работы ∑ k(v) (log (m / k(v)) + 1)
4. Использование в Link-Cut : суммарное время Expose = O(logn)

5. Корневая

1. split/rebuild, split/merge на примере reverse/insert
2. отложенные операции (lazy propagation) на примере сортированного массива

6. DCP Offline

1. Удаления можно свести к добавлениям, получили решение с DSU за log2
2. Корневая по запросам за O(m3/2)
3. [skipped] DCP Offline за O(mlogm)

7. [skipped] Дополнительно: ещё про деревья

1. [skipped] HLD
2. [skipped] Centroid (и минимум на пути за O(1))
3. [skipped] Сливаемые множества

8. [skipped] 2D-деревья
9. [skipped] Мо