Задачи RMQ и LCA
Вторник, 27 ноября 2018
Таймс, ауд. 405
Динамическая задача RMQ/RSQ: дерево отрезков,
оценка \(O(\log n)\) для запросов суммы/минимума и изменения элемента.
Статический вариант задачи RMQ: полное предвычисление
(\(O(n^2)\) на предобработку, \(O(1)\) на запрос),
метод разреженной таблицы (\(O(n\log n)\) на предобработку, \(O(1)\) на
запрос).
Задача LCA: эйлеров обход дерева, сведение к задаче RMQ.