RMQ и LCA (14 мая 2018)

1. Задача RMQ
1. Формулировка, решение деревом отрезков
2. "Lower bound on Time" для меняющегося массива через сортировку
3. Sparse Table и модификации
1. Sparse Table за [O(nlogn), O(1)]. Неизменяемость vs изменяемость.
2. Подходит для любой идемпотентной коммутативной ассоциативной функции. Примеры функций: min, gcd, sum
3. Модифицируем структуру до [O(n), O(logn)], [O(nloglogn), O(1)], [O(n), O(loglogn)]


2. Алгоритм Фараха-Колтона-Бендера
1. RMQ → LCA (построение декартова дерева за линейное время)
2. LCA → RMQ±1 (Эйлеров обход, 3 версии обхода)
3. Решение задачи RMQ±1 с помощью четырёх русских


3. Замечания
1. LCA мы умеем считать SparseTable-ом за O(1)
2. Поддерево = отрезок эйлерова обхода, функция от поддерева = функция на отрезке

1. LCA
1. Обход дерева, глубины, времена входа-выхода, isAncestor in O(1)
2. LCA двоичными подъёмами за [O(nlogn), O(logn)]
3. LCA а offline Тарьяном за O((n+m)α)


2. LA (Level Ancestor)
1. Предподсчитаем всё (n², 1).
2. Уже умеем: двоичные подъёмы (nlogn, logn)
3. Алгоритм Вишкина за [O(n), O(logn)]
4. [skipped] [в ДЗ] Уже умеем делать: Offline за O(n+m);
5. [skipped] Упражнение: использовать 4-х русских, чтобы получить [O(n), O(1)]


3. Euler-Tour-Tree

1. LA за O(1)
1. longest-path decomposition, ladder decomposition [O(nlogn), O(1)]
2. Идея: храним подъёмы только от листьев (предподсчёт: dfs в offline)
3. Микро-макро эвристика (4 русских): обрубаем все поддеревья размера менее logn/4