Задачи поиска ближайшего общего предка (LCA) и минимума на отрезке (RMQ)

Понедельник, 16 февраля 2015
Таймс, ауд. 404

Описание

  • Задачи на поддеревьях
    • Дерево. Поддеревья, листья, отношение предок-потомок, корень
    • Эйлеров обход дерева. Время входа и выхода
    • Двоичные подъемы
    • Задачи LCA и LA
  • Задача RMQ
    • Формулировка, варианты решения. Разреженные таблицы
  • Алгоритм Фарах-Колтона и Бендера
    • Сведение LCA к RMQ+-1
    • Решения RMQ+-1 за O(1) с предпосчетом за O(N)
  • Сведение RMQ к LCA