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

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

<br>
# LCA, RMQ: возможно, новое
## Улучшаем sparse table до [nloglogn, 1] и [n, loglogn], рекурсивно замыкаем
## Решение RMQ&pm;1 за [n, 1] четырьмя русскими
## RMQ &rarr; LCA &rarr; RMQ&pm;1 (Построение Декартового дерева, Эйлеров обход)
## Другое использование Эйлерова обхода: функция от поддерева

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

@Pause

# LCA: алгоритм Тарьяна.

<br>
# Дерево отрезков снизу
## Описание, запросы get, change
## Сравнение с реализацией сверху

<br>
# Задачи
## += на отрезке через сумму на отрезке
## Сумма на пути дерева = префиксные суммы
## Сумма на пути, изменение в ребре = эйлеров обход, рёбра с разными знаками
## Сумма на пути, изменение в вершине = два эйлеровых обхода (по времени входа, по времени выхода)
## Биекция между вершинами и рёбрами
## Сумма на пути, += на пути : все пути во всех запросах до корня 
## Минимум на пути в дереве без изменений в offline : через сортировку рёбер и СНМ
## Минимум на пути в дереве без изменений в offline : через сортировку запросов и СНМ

<br>
*# Дополнительное
*## RMQ.Offline: напрямую без RMQ &rarr; LCA 
*## Disjoint Sparse Table
*## Задача: даны два подвешенных дерева, номера вершин различны, запрос -- найти размер пересечения двух поддеревьев

