LA, Heavy-Light Decomposition, Euler tour trees (5 марта 2016)

1. LA (Level Ancestor)
1. Предподсчитаем всё (n², 1).
2. Уже умеем делать: Offline за O(n+m); Двоичные подъёмы (nlogn, logn)
3. Алгоритм Вишкина за [O(n), O(logn)]. Упражнение: использовать 4-х русских, чтобы получить [O(n), O(1)]
4. longest-path decomposition, ladder decomposition [O(nlogn), O(1)]
5. Идея: храним двоичные подъёмы только от листьев (предподсчёт: dfs в offline)
6. Микро-макро эвристика (4-русских): обрубаем все поддеревья размера менее logn/4
2. Euler Tour Trees
1. идея, Эйлеров Обход Дерева, содержащий ориентированные рёбра
2. ребро дерево ↔ вершина treap
3. вершина дерева → рёбра дерева
4. ребро → обратное ребро
5. get(v): вершина дерева → ребро → вершина treap → подняться до корня treap
6. makeRoot(v): start = any outgoing edge
7. link(a, b): makeRoot(a), makeRoot(b), concat
8. cut(a, b): makeRoot(a), e = (a, b), split off [e..rev(e)]
3. Heavy-Light decomposition
1. идея
2. лемма про число прыжков
3. тонкости реализации (как создать HLD, как прыгать по ней)
4. общая идея решения задач: сперва решить на отрезке массива, затем обобщить до дерева, heavy-light обычно нужен только если дерево меняется
4. Link-Cut-Tree: общая идея без доказательства