Изменения

'''Метод двоичного подъемаподъёма''' {{---}} один из самых простых методов для решения задачи [[Сведение задачи LCA к задаче RMQ|LCA]] в on-lineonline. Он не использует метод решение решения задачи '''RMQ''' и основан на методе [[Динамическое программирование | динамического программирования]].

Препроцессинг заключается в том, чтобы посчитать функцию: <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> есть рекуррентная формула:

dp[dp[v][i - 1]][i - 1] & i \: > \: 0.

Для того чтобы отвечать на запросы нам нужны будут только те значения <tex> dp[v][i] </tex>, где <tex> i \le leqslant \log_2{n} </tex>, ведь при больших <tex> i </tex> значение <tex> dp[v][i] </tex> будет номером корня.

Для ответа на запрос заметим сначала, что если <tex> c = LCA(v, u) </tex>, для некоторых <tex> v </tex> и <tex> u </tex>, то <tex> d[c] \le leqslant \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> ji_j</tex> пройти вверх последовательно из вершины <tex> u </tex> в <tex> dp[u][i_j] </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> 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> '''function''' preprocess(): '''int[]''' p := dfs(0) '''for ''' i := 1 .. '''to''' n dp[i][0] := p[i] '''for ''' j := 1 .. '''to''' log(n) '''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)] swap(v, u) '''for ''' i := log(n) .. '''downto''' 0 '''if (''' d[dp[u][i]] - d[v] >= <tex> 2 ^ i </tex>)0 u := dp[u][i] '''if (''' v == u) '''return ''' v '''for ''' i := log(n) .. '''downto''' 0 '''if (''' dp[v][i] <> != dp[u][i]) v := dp[v][i] u := dp[u][i] '''return ''' p[v]</big>

 ==Источники информации==* [http://ruen.wikipedia.org/wiki/Lowest_common_ancestor Wikipedia: LCA LCA on Wikipedia]

* [http://e-maxx.ru/algo/lca_simpler MAXimal :: algo :: Метод двоичного подъема - e-maxx.ruподъёма ]