RMQ и LCA (14 мая 2021)

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)]
   4. Разбиение на отрезки: дерево отрезков бьёт любой отрезок на logn отрезков, SparseTable покрывает двумя
   
   
2. Алгоритм Фараха-Колтона-Бендера
   1. RMQ → LCA (построение декартова дерева за линейное время)
   2. LCA → RMQ±1 (Эйлеров обход, 3 версии обхода)
   3. Решение задачи RMQ±1 с помощью четырёх русских
      1. Максимально грубый прекалк
      2. Прекалк за 2^k
   
   
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. [skipped] Доплекция: LA за O(1)
   1. [skipped] longest-path decomposition, ladder decomposition [O(nlogn), O(1)]
   2. [skipped] Идея: храним подъёмы только от листьев (предподсчёт: dfs в offline)
   3. [skipped] Микро-макро эвристика (4 русских): обрубаем все поддеревья размера менее logn/4