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

Бабенко Максим рассказывает о задачах 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: эйлеров обход дерева.