Изменения
Нет описания правки
{{В разработке}}
Метод двоичного подъема {{- --}} это один из самых простых методов для решения задачи [[Сведение задачи LCA к задаче RMQ|LCA ]] в on-line и он не использует метод решение задачи RMQ. Он основан на методе динамического программирования.
==Описание алгоритма==
Как и все on-line алгоритмы, этот метод делает сначала препроцессинг, чтобы потом отвечать на запросы.
===Препроцессинг===
Препроцессинг заключается в том, чтобы посчитать функцию: <tex> dp[v][i] </tex> {{- --}} это номер вершины, в которую мы придем если пройдем из вершины <tex> v </tex> вверх по подвешенному дереву <tex> 2 ^ i </tex> шагов, причем если мы пришли в корень, то мы там и останемся.Для этого сначала обойдем дерево в глубину и для каждой вершины запишем номер ее родителя <tex> p[v] </tex> и глубину вершины в подвешенном дереве <tex> depthd[v] </tex>. Если <tex> v </tex> - корень, то <tex> p[v] = v </tex>. Тогда для функции <tex> dp </tex> есть рекуррентная формула:
<tex>dp[v][i]= \begin{cases}
\end{cases}</tex>
Для того чтобы отвечать на запросы нам нужны будут только те значения <tex> dp[v][i] </tex>, где <tex> i \le \log_2{n} </tex>, ведь при больших <tex> i </tex> значение <tex> dp[v][i] </tex> будет номером корня. Всего состояний динамики <tex> O(n \log{n})</tex>, где <tex> n </tex> {{---}} это количество вершин в дереве. Каждое состояние считается за <tex> O(1) </tex>. Поэтому суммарная сложность времени и памяти препроцессинга {{---}} <tex> O(n \log{n}) </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[v] = d[u] </tex>.
Если <tex> v = u </tex>, то ответ на запрос <tex> v </tex>.
А если <tex> v \neq u </tex>, то найдем такие вершины <tex> x </tex> и <tex> y </tex>, такие что <tex> x \neq y </tex>, <tex> x </tex> {{---}} предок <tex> v </tex>, <tex> y </tex> {{---}} предок <tex> u </tex> и <tex> p[x] = p[y] </tex>. Тогда ответом на запрос будет <tex> p[x] </tex>.
Научимся находить эти вершины <tex> x </tex> и <tex> y </tex>. Для этого сначала инициализируем <tex> x = v </tex> и <tex> y = u </tex>. Дальше на каждом шаге находим такое максимальное <tex> k </tex>, что <tex> dp[x][k] \neq dp[y][k] </tex>. И проходим из вершин <tex> x </tex> и <tex> y </tex> на <tex> 2 ^ k </tex> шагов вверх. Если такого <tex> k </tex> найти нельзя, то значения <tex> x </tex> и <tex> y </tex>, это те самые вершины, которые нам требуется найти, ведь <tex> p[x] = dp[x][0] = dp[y][0] = p[y] </tex>.
Оценим время работы. Заметим, что найденные <tex> k </tex> строго убывают. Во-первых, потому что мы находим на каждом шаге максимальное значение <tex> k </tex>, а во-вторых, два раза подряд мы одно и то же <tex> k </tex> получить не можем, так как тогда получилось бы, что можно пройти <tex> 2 ^ k + 2 ^ k = 2 ^ {k + 1}</tex> шагов, а значит вместо первого <tex> k </tex>, мы бы нашли <tex> k + 1 </tex>. А значит всего <tex> O(\log{n}) </tex> значений <tex> k </tex>, их можно перебирать в порядке убывания. Сложность ответа на запрос <tex> O(\log{n}) </tex>.
==Псевдокод==
<big><big>
preprocess()
p := dfs(0)
for i := 1 .. n
dp[i][0] := p[i]
for j := 1 .. log(n)
for i := 1 .. n
dp[i][j] := dp[dp[i][j - 1]][j - 1]
lca(v, u)
if (v > u)
swap(v, u)
for i := log(n) .. 0
if (d[u] - d[v] >= <tex> 2 ^ i </tex>)
u := dp[u][i]
if (v = u)
return v
for i := log(n) .. 0
if (dp[v][i] <> dp[u][i])
v := dp[v][i]
u := dp[u][i]
return p[v]
</big></big>
