$ RMQ & LCA
vb = [Ваня]
sk = [Сережа.K]
Соц.опрос: языки программирования С/C++, Java, Python, Pascal
# [05] $sk$ С/C++: структура с битовым сжатием
# [10] $vb$ RMQ деревом отрезков за [n, logn] (минимум на отрезке, изменение в точке, реализация сверху)
# [10] $vb$ RMQ через sparse table за [nlogn, 1]
# [05] $vb$ Проверка, является одна вершина предком другой за O(1)
# [17] $vb$ Двоичные подъемы: LCA за [nlogn, logn] (двумя способами)
# [---] $vb$ Упражнение: посчитать двоичными подъемами глубину вершины за logn
# [15] $vb$ LCA → RMQ±1 (Эйлеров обход дерева)
# [03] $vb$ LCA мы теперь тоже умеем за [nlogn, 1] (LCA → RMQ, sparse table)
Перерыв
# [20] $sk$ RMQ → LCA (строим декартово дерево)
# [05] $sk$ LCA в Offline за O((n+m)*) (алгоритм Ахо-Ульмана-Тарьяна)
# [05] $sk$ минимум на пути в дереве в Online: двоичные подъемы [nlogn, logn]
# [05] $sk$ Sparse table за [n, logn]
# [05] $sk$ Sparse table за [n, log*n] (рекурсивное замыкание предыдущей идеи)
# [10] $sk$ Фарах-Колтон-Бендер: RMQ → LCA → RMQ±1 и алгоритм 4-х русских для решения последней