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

# Persistent: сборка мусора 
## Задача: копирование памяти
## Варианты сборки: стек, список

<br>
# ETT = Euler-Tour-Tree (Acyclic Dynamic Connectivity Online)
## Подробно про реализацию, так как будет задача в контесте

<br>
# Link-Cut-Tree
## Expose, потенциал, logn вызовов split/merge
## MakeRoot, Link, Cut функция на пути

<br>
# Splay деревья
## Операция Splay, выражение через неё Split, Merge, Add, Del
*## Доказательство времени работы 3(log R(v) - log R(u)) + 1
*## Доказательство времени работы &sum; k(v) (log (m / k(v)) + 1)
## Использование в Link-Cut : суммарное время Expose = O(logn)

<br>
# Корневая
## split/rebuild, split/merge на примере reverse/insert
## отложенные операции (lazy propagation) на примере сортированного массива

<br>
# DCP Offline
## Удаления можно свести к добавлениям, получили решение с DSU за log^2
## Корневая по запросам за O(m^{3/2})
*## DCP Offline за O(mlogm)

<br>
*# Дополнительно: ещё про деревья
*## HLD
*## Centroid (и минимум на пути за O(1))
*## Сливаемые множества

<br>
*# 2D-деревья
*# Мо
