97
правок
Изменения
Нет описания правки
'''Метод двоичного подъема''' {{---}} один из самых простых методов для решения задачи [[Сведение задачи LCA к задаче RMQ|LCA]] в online. Он не использует метод решение задачи '''RMQ''' и основан на методе [[Динамическое программирование | динамического программирования]].
==Описание алгоритма==
Как и большинство '''on-line''' алгоритмов для решения задачи [[Сведение задачи LCA к задаче RMQ|LCA]], этот метод делает сначала препроцессинг, чтобы потом отвечать на запросы.
<tex>dp[v][i]= \begin{cases}
p[v] & i = 0,\\
dp[dp[v][i - 1]][i - 1] & i > \textgreater 0.
\end{cases}</tex>
===Ответы на запросы===
Ответы на запросы будут происходить за время <tex> O(\log{n})</tex>.
Для ответа на запрос заметим сначала, что если <tex> c = LCA(v, u) </tex>, для некоторых <tex> v </tex> и <tex> u </tex>, то <tex> d[c] \le \min(d[v], d[u])</tex>. Поэтому если <tex> d[v] < d[u] </tex>, то пройдем от вершины <tex> u </tex> на <tex> (d[u] - d[v]) </tex> шагов вверх, это и будет новое значение <tex> u </tex> и это можно сделать за <tex> O(\log{n}) </tex>. Можно записать число <tex> (d[u] - d[v]) </tex> в двоичной системе, это представление этого число в виде суммы степеней двоек, <tex> 2 ^ {i_1} + 2 ^ {i_2} + \ldots + 2 ^ {i_l} </tex> и для всех <tex> i_j</tex> пройти вверх последовательно из вершины <tex> u </tex> в <tex> dp[u][i_j] </tex>.
Дальше считаем, что <tex> d[v] = d[u] </tex>.
'''for''' i = 1 '''to''' n
dp[i][j] = dp[dp[i][j - 1]][j - 1]
'''int''' lca('''int''' v, '''int''' u):
'''if''' d[v] > d[u]
'''return''' p[v]
</code>
==См. также==
* [[Сведение задачи LCA к задаче RMQ]]
==Источники информации==
* [[wikipedia:LCA | Wikipedia {{---}} LCA]]
* [http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor TopCoder tutorial: RMQ and LCA]
