Изменения
Новая страница: «== Постановка задачи LCA == {{Определение |definition = '''Наименьший общий предок (least common ancestor)''' дву…»
== Постановка задачи LCA ==
{{Определение
|definition = '''Наименьший общий предок (least common ancestor)''' двух узлов <tex>u, v</tex> в корневом дереве <tex>T</tex> - это такой узел <tex>w</tex>, который среди всех узлов, являющихся предками как узла <tex>u</tex>, так и <tex>v</tex>, имеет наибольшую глубину.
}}
== См.также ==
*[[Метод двоичного подъема]]
*[[Решение RMQ с помощью разреженной таблицы]]
*[[Алгоритм Фарака-Колтона и Бендера]]
*[[Сведение задачи RMQ к задаче LCA]]
{{Определение
|definition = '''Наименьший общий предок (least common ancestor)''' двух узлов <tex>u, v</tex> в корневом дереве <tex>T</tex> - это такой узел <tex>w</tex>, который среди всех узлов, являющихся предками как узла <tex>u</tex>, так и <tex>v</tex>, имеет наибольшую глубину.
}}
== См.также ==
*[[Метод двоичного подъема]]
*[[Решение RMQ с помощью разреженной таблицы]]
*[[Алгоритм Фарака-Колтона и Бендера]]
*[[Сведение задачи RMQ к задаче LCA]]
