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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «== Постановка задачи LCA == {{Определение |definition = '''Наименьший общий предок (least common ancestor)''' дву…»)
 
Строка 1: Строка 1:
 
== Постановка задачи LCA ==
 
== Постановка задачи LCA ==
 
{{Определение  
 
{{Определение  
|definition = '''Наименьший общий предок (least common ancestor)''' двух узлов <tex>u, v</tex> в корневом дереве <tex>T</tex> - это такой узел <tex>w</tex>, который среди всех узлов, являющихся предками как узла <tex>u</tex>, так и <tex>v</tex>, имеет наибольшую глубину.
+
|definition = '''Наименьший общий предок (least common ancestor)''' двух узлов <tex>u, v</tex> в корневом дереве <tex>T</tex> - это такой узел <tex>w,</tex> который среди всех узлов, являющихся предками как узла <tex>u,</tex> так и <tex>v,</tex> имеет наибольшую глубину.
 
}}
 
}}
 +
Пусть дано корневое дерево <tex>T.</tex> На вход подаются запросы вида <tex>(u,\;v),</tex> для каждого запроса требуется найти их наименьшего общего предка.
  
  

Версия 05:45, 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] для каждого запроса требуется найти их наименьшего общего предка.


См.также