Изменения

Перейти к: навигация, поиск

Сведение задачи LCA к задаче RMQ

14 байт добавлено, 23:31, 1 июня 2012
Постановка задачи LCA: punctuation fixup
== Постановка задачи LCA ==
{{Определение
|definition = '''Наименьшим общим предком (least common ancestor)''' двух узлов <tex>u, </tex> и <tex>v</tex> в корневом дереве <tex>T</tex> называется узел <tex>w,</tex> , который среди всех узлов, являющихся предками как узла <tex>u,</tex> , так и <tex>v,</tex> , имеет наибольшую глубину.
}}
Пусть дано корневое дерево <tex>T.</tex> . На вход подаются запросы вида <tex>(u,\;v),</tex> , для каждого запроса требуется найти их наименьшего общего предка.
== Алгоритм ==
Анонимный участник

Навигация