Сведение задачи 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> | + | |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) двух узлов в корневом дереве - это такой узел который среди всех узлов, являющихся предками как узла так и имеет наибольшую глубину. |
Пусть дано корневое дерево На вход подаются запросы вида для каждого запроса требуется найти их наименьшего общего предка.
