Лекция 4. LCA и RMQ

Четверг, 30 сентября 2021
Таймс, 2 этаж, ауд.204

Описание

  1. Задача LCA поиска нижайшего общего предка двух вершин в подвешенном дереве. Решение с $\mathcal O(n\log n)$ препроцессинга и памяти, $\mathcal O(1)$ на запрос: двоичные подъёмы.

  2. Задача RMQ поиска минимума на подотрезках массива. Сведение LCA к RMQ за $\mathcal O(n)$: эйлеров обход.

  3. LCA и RMQ с $\mathcal O(n)$ препроцессинга и памяти, $\mathcal O(\log n)$ на запрос: дерево отрезков.

  4. LCA и RMQ с $\mathcal O(n\log n)$ препроцессинга и памяти, $\mathcal O(1)$ на запрос: разреженная таблица.

  5. LCA и частный случай RMQ с $\mathcal O(n)$ препроцессинга и памяти, $\mathcal O(1)$ на запрос: алгоритм Фараха-Колтона, Бендера.