## ЛКШ 2018, 1-й день, LCA, RMQ, LA, Euler-Tour (Сергей Копелиович)

1. LCA, RMQ: простое

1. LCA двоичными подъёмами: два способа; проверка "является ли предком"
2. RMQ разреженными таблицами: [nlogn, 1]

2. LCA, RMQ: возможно, новое

1. Улучшаем sparse table до [nloglogn, 1] и [n, loglogn], рекурсивно замыкаем
2. Решение RMQ±1 за [n, 1] четырьмя русскими
3. RMQ → LCA → RMQ±1 (Построение Декартового дерева, Эйлеров обход)
4. Другое использование Эйлерова обхода: функция от поддерева

3. LA

1. LA.Offline
2. LA.Online [O(n), O(logn)] − алгоритм Вишкина
3. LA.Online [O(nlogn), O(1)] − лестничная декомпозиция
4. [skipped] LA.Online [O(n), O(1)] − добавляем эйлеров обход и 4 русских

− Перерыв −

1. LCA: алгоритм Тарьяна.
2. Дерево отрезков снизу

1. Описание, запросы get, change
2. Сравнение с реализацией сверху

3. Задачи

1. += на отрезке через сумму на отрезке
2. Сумма на пути дерева = префиксные суммы
3. Сумма на пути, изменение в ребре = эйлеров обход, рёбра с разными знаками
4. Сумма на пути, изменение в вершине = два эйлеровых обхода (по времени входа, по времени выхода)
5. Биекция между вершинами и рёбрами
6. Сумма на пути, += на пути : все пути во всех запросах до корня
7. Минимум на пути в дереве без изменений в offline : через сортировку рёбер и СНМ
8. Минимум на пути в дереве без изменений в offline : через сортировку запросов и СНМ

4. [skipped] Дополнительное

1. [skipped] RMQ.Offline: напрямую без RMQ → LCA
2. [skipped] Disjoint Sparse Table
3. [skipped] Задача: даны два подвешенных дерева, номера вершин различны, запрос − найти размер пересечения двух поддеревьев