Задачи RMQ и LCA (3 марта)

1. Сканирующая прямая
1. Общая схема, на какие запросы мы умеем по-простому отвечать
2. Площадь объединения прямоугольников
2. Sparse Table и модификации
1. Sparse Table [O(nlogn), O(1)]. Неизменяема. Подходит для любой идемпотентной коммутативной ассоциативной функции.
2. Disjoint Sparse Table [O(nlogn), O(1)]. Неизменяема. Подходит для любой ассоциативной функции.
3. Примеры функций: min, gcd, sum, произведение, композиция перестановок, сумма векторов, максимум векторов
4. Модифицируем структуру до [O(n), O(logn)], [O(nloglogn), O(1)], [O(n), O(loglogn)]
3. Алгоритм Фараха-Колтона-Бендера
1. RMQ → LCA (построение декартова дерева за линейное время)
2. LCA → RMQ±1 (Эйлеров обход, 3 версии обхода)
3. Решение задачи RMQ±1 с помощью четырёх русских
4. Замечания: LCA мы умеем считать SparseTable-ом за O(1), поддерево = отрезок, функция от поддерева = функция на отрезке
4. LCA
1. Обход дерева, глубины, времена входа-выхода, isAncestor in O(1)
2. LCA двоичными подъёмами за [O(nlogn), O(logn)]