RMQ и LCA (17 мая 2017)

  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)]
  2. LA (Level Ancestor)
    1. Предподсчитаем всё (n2, 1).
    2. Уже умеем: двоичные подъёмы (nlogn, logn)
    3. Алгоритм Вишкина за [O(n), O(logn)]
  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