Алгоритмы и структуры данных поиска: Задачи RMQ и LCA. Бабенко Максим

960

Бабенко Максим рассказывает о задачах RMQ и LCA.

  1. Задачи RMQ (range minimum query) и LCA (least common ancestor).
  2. Сведение от задачи RMQ к задаче LCA, декартово дерево.
  3. Алгоритм Таржана для offline-версии задачи LCA.
  4. Простейшие алгоритмы для online-версии задачи LCA: полная и разреженная таблицы ответов.
  5. Алгоритм Фарах-Колтона-Бендера для к задаче ±1-RMQ.
  6. Сведение задачи LCA к задаче ±1-RMQ: эйлеров обход дерева.