105
правок
Изменения
м
Нет описания правки
'''Метод двоичного подъемаподъёма''' {{---}} один из самых простых методов для решения задачи [[Сведение задачи LCA к задаче RMQ|LCA]] в online. Он не использует метод решение задачи '''RMQ''' и основан на методе [[Динамическое программирование | динамического программирования]].
==Описание алгоритма==
Как и большинство '''on-line''' алгоритмов для решения задачи [[Сведение задачи LCA к задаче RMQ|LCA]], этот метод делает сначала препроцессинг, чтобы потом отвечать на запросы.
===Препроцессинг===
Препроцессинг заключается в том, чтобы посчитать функцию: <tex> dp[v][i] </tex> {{---}} номер вершины, в которую мы придем если пройдем из вершины <tex> v </tex> вверх по подвешенному дереву <tex> 2 ^ i </tex> шагов, причем причём если мы пришли в корень, то мы там и останемся.Для этого сначала обойдем дерево в глубину и для каждой вершины запишем номер ее её родителя <tex> p[v] </tex> и глубину вершины в подвешенном дереве <tex> d[v] </tex>. Если <tex> v </tex> {{---}} корень, то <tex> p[v] = v </tex>. Тогда для функции <tex> dp </tex> есть рекуррентная формула:
<tex>dp[v][i]= \begin{cases}
* [http://en.wikipedia.org/wiki/Lowest_common_ancestor Wikipedia: LCA]
* [http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor TopCoder tutorial: RMQ and LCA]
* [http://e-maxx.ru/algo/lca_simpler MAXimal :: algo :: Метод двоичного подъема подъёма ]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о наименьшем общем предке]]
