Раздел «Образование».FIVTLecturesTerm3Lecture6:
<< Список лекций ФИВТ, 3-й семестр, 2009 г.

Лекция 6. Задачи RMQ и LCA. Сведение этих задач друг к другу

Задача Lowest Common Ancestor (LCA)

Дано ориентированное дерево. Выполнив некоторые подготовительные вычисления (preprocessing) необходимо макимаьно быстро для любых двух вершин дерева возвращать вершину, которая является общим предшественником (ancestor) и имеет максимальную глубину (lowest).

Сведение LCA к RMQ

Осуществляем эйлеров обход дерева во время которого строим массив W пар (вершина, глубина) (записываем в конец вершину, которую посещаем).

Во время обхода некоторые вершины (а именно, внутренние) попадают в этот массив несколько раз. Но итоговая длина массива P ограничена O(n), где n - число вершин в дереве.

Также во время обхода строим хештаблицу H "Вершина" -> "индекс в массиве P, где впервые встретилась эта вершина".

Пусть даны две вершины v и u. Пусть i = H[v]; j = H[u]. Решаем RMQ для полуинтервала [i, j+1) на массиве B.

Сведение RMQ к LCA

Декартово дерево. Задача постоения декартового дерева за линейное время.

Решение задачи RMQ за время (препроцессинг=O(n), запрос O(1))