Сведение задачи LCA к задаче RMQ — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 5: Строка 5:
 
Пусть дано корневое дерево <tex>T.</tex> На вход подаются запросы вида <tex>(u,\;v),</tex> для каждого запроса требуется найти их наименьшего общего предка.
 
Пусть дано корневое дерево <tex>T.</tex> На вход подаются запросы вида <tex>(u,\;v),</tex> для каждого запроса требуется найти их наименьшего общего предка.
  
 +
== Алгоритм ==
 +
=== Препроцессинг ===
 +
1) В каждом узле будет храниться глубина узла в корневом дереве <tex>T.</tex>
 +
:<tex>depth(u)= \begin{cases}
 +
0 & u = root(T),\\
 +
depth(v) + 1 & u = son(v).
 +
\end{cases}</tex>
 +
 +
2) Ориентируем каждое ребро в дереве <tex>T</tex> и добавим обратное к этому ребру. Получим эйлеров граф <tex>E.</tex>. Найдем в графе <tex>E</tex> эйлеров цикл, записывая в массив глубину посещенных узлов.
 +
 +
3) Построим дерево отрезков по полученному массиву.
  
 
== См.также ==
 
== См.также ==

Версия 07:25, 25 марта 2011

Постановка задачи LCA

Определение:
Наименьший общий предок (least common ancestor) двух узлов [math]u, v[/math] в корневом дереве [math]T[/math] - это такой узел [math]w,[/math] который среди всех узлов, являющихся предками как узла [math]u,[/math] так и [math]v,[/math] имеет наибольшую глубину.

Пусть дано корневое дерево [math]T.[/math] На вход подаются запросы вида [math](u,\;v),[/math] для каждого запроса требуется найти их наименьшего общего предка.

Алгоритм

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

1) В каждом узле будет храниться глубина узла в корневом дереве [math]T.[/math]

[math]depth(u)= \begin{cases} 0 & u = root(T),\\ depth(v) + 1 & u = son(v). \end{cases}[/math]

2) Ориентируем каждое ребро в дереве [math]T[/math] и добавим обратное к этому ребру. Получим эйлеров граф [math]E.[/math]. Найдем в графе [math]E[/math] эйлеров цикл, записывая в массив глубину посещенных узлов.

3) Построим дерево отрезков по полученному массиву.

См.также