Лекция 9. Задачи RMQ и LCA (Алгоритмы и структуры данных, часть 1)

Статические задачи RMQ/RSQ (range minimum/sum query) и LCA (least common ancestor). Оптимальное решение задачи RSQ. Решение задачи LCA методом бинарного подъёма (O(NlogN) памяти, запрос за O(logN) времени). Сведение от задачи RMQ к задаче LCA: декартово дерево. Сведение задачи LCA к задаче ±1-RMQ: Эйлеров обход дерева. Простейшие алгоритмы для решения задачи RMQ: полная и разреженная таблицы ответов. Алгоритм Фарах-Колтона-Бендера для задачи ±1-RMQ: деление массива на блоки, предподсчёт для префиксов и суффиксов блоков, предподсчёт всех нормализованных блоков. Алгоритм Тарьяна для поиска LCA в режиме offline Лекция №9 в курсе "Алгоритмы и структуры данных, часть 1", осень 2018 (Новосибирск) Преподаватели курса: Александр Александрович Стененко, Степан Юрьевич Гатилов Страница лекции на сайте CS центра: https://compscicenter.ru/courses/algorithms-1/nsk/2018-autumn/classes/4377/ Все видео курса по порядку: https://www.youtube.com/playlist?list=PLlb7e2G7aSpSvqoUtSFrhZ-wAyfrQ9lMd