Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
прога_билеты.docx
Скачиваний:
4
Добавлен:
01.03.2025
Размер:
3 Мб
Скачать
☆

Сведение rmq к lca и наоборот.

LCA (least common ancestor)

Задача LCA (наименьший общий предок) для двух вершин  и  в корневом дереве  называется узел , который среди всех узлов, являющихся предками как узла , так и , имеет наибольшую глубину. Пусть дано корневое дерево . На вход подаются запросы вида , для каждого запроса требуется найти их наименьшего общего предка. Четыре основных алгоритма:

  1. Самый простой, наивный алгоритм для нахождения наименьшего общего предка — вычислить глубину вершин u и v и постепенно подниматься из каждой вершины вверх по дереву, пока не будет найдена общая вершина:

Процедура LCA(u, v):

h1 := depth(u) // depth(x) = глубина вершины x

h2 := depth(v)

while h1 ≠ h2:

if h1 > h2:

u := parent(u)

h1 := h1 - 1

else:

v := parent(v)

h2 := h2 - 1

while u ≠ v:

u := parent(u) // parent(x) = непосредственный предок вершины x

v := parent(v)

return u

Время работы этого алгоритма составляет O(h), где h — высота дерева. Кроме того, может понадобиться препроцессинг, требующий O(n) времени, для нахождения непосредственного предка для всех вершин дерева и глубины вершин (но, как правило, эта структура на дереве уже имеется) – делается обходом графа.

  1. Алгоритм за O(sqrt(H)). шаг первый: BFS – узнаем глубину дерева и глубину каждой из вершин

Шаг второй: DFS – Делим на уровни длиной sqrt(H) (их всего будет sqrt(H)). Для каждой вершины считаем d[v] = первый предок из предыдущего уровня.

Как считать? Если глубина вершины кратна sqrt(H), значит они или первая, или последняя в уровне – обрабатываем отдельно. Иначе d[v] = d[u], где u – прямой предок v. Итого предпроцессинг за O(H). Запрос:

Если вершины на разных уровнях – прыгаем из вершины с меньшим уровнем, пока уровень не будет одинаковым (максимум – O(sqrtH)). Когда достигли одного уровня, то P[v] = P[u], то LCA u,v находится между ними и вершиной P[u] = P[v]. Просто поднимаемся вверх (по прямым родителям), пока не окажемся в одной вершине. Если P[u] != P[v] – максимум за O(sqrt(H)).

Итого алгоритм работает за <O(N), O(sqrtH)>

  1. Метод двоичного подъема Данный алгоритм является on-line (то есть сначала делается препроцессинг, затем алгоритм работает в формате запрос-ответ).

Препроцессинг

Препроцессинг заключается в том, чтобы посчитать функцию:  — номер вершины, в которую мы придем если пройдем из вершины  вверх по подвешенному дереву  шагов, причем если мы пришли в корень, то мы там и останемся. Для этого сначала обойдем дерево в глубину и для каждой вершины запишем номер ее родителя  и глубину вершины в подвешенном дереве . Если  — корень, то . Тогда для функции  есть рекуррентная формула:

Ведь 2i-1+2i-1=2i Для того чтобы отвечать на запросы нам нужны будут только те значения , где , ведь при больших  значение  будет номером корня. Всего состояний динамики , где  — это количество вершин в дереве. Каждое состояние считается за . Поэтому суммарная сложность времени и памяти препроцессинга — .