RMQ и LCA (20 мая 2025)

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)] (log* не делаем, ушло на практику).
   4. Разбиение на отрезки: дерево отрезков бьёт любой отрезок на logn отрезков, SparseTable покрывает двумя
   5. Решение задачи RMQ±1 с помощью четырёх русских: максимально грубый прекалк (прекалк за 2^k не делаем, ушло в практику)
   6. Решение задачи RMQ за O(n) разбиением на куски размера w=64
   
   
2. LCA
   1. Обход дерева, глубины, времена входа-выхода, isAncestor in O(1)
   2. LCA двоичными подъёмами за [O(nlogn), O(logn)]
   3. LCA → RMQ±1 (Эйлеров обход), LCA SparseTable-ом за O(1)

1. Более сложные алгоритмы
   1. RMQ → LCA (построение декартова дерева за линейное время)
   2. Фарах-Колтон-Бендер: RMQ → LCA → RMQ±1 → O(n)
   3. LCA в offline Тарьяном за O((n+m)α)
   4. Эйлеров обход: версия 2. Поддерево = отрезок эйлерова обхода, функция от поддерева = функция на отрезке
   5. Эйлеров обход: версия 3. Прелюдия к ETT.
   6. ETT: link-cut-isconnected
   
   
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)]

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