Метод двоичного подъёма — различия между версиями
м (→Ответы на запросы: comas added) |
|||
Строка 53: | Строка 53: | ||
'''return''' p[v] | '''return''' p[v] | ||
</code> | </code> | ||
+ | |||
+ | ==Модификация предподсчета за O(n)== | ||
+ | |||
==См. также== | ==См. также== |
Версия 19:00, 7 мая 2016
Метод двоичного подъема — один из самых простых методов для решения задачи LCA в online. Он не использует метод решение задачи RMQ и основан на методе динамического программирования.
Содержание
Описание алгоритма
Как и большинство on-line алгоритмов для решения задачи LCA, этот метод делает сначала препроцессинг, чтобы потом отвечать на запросы.
Препроцессинг
Препроцессинг заключается в том, чтобы посчитать функцию:
— номер вершины, в которую мы придем если пройдем из вершины вверх по подвешенному дереву шагов, причем если мы пришли в корень, то мы там и останемся. Для этого сначала обойдем дерево в глубину и для каждой вершины запишем номер ее родителя и глубину вершины в подвешенном дереве . Если — корень, то . Тогда для функции есть рекуррентная формула:
Для того чтобы отвечать на запросы нам нужны будут только те значения
, где , ведь при больших значение будет номером корня.Всего состояний динамики
, где — это количество вершин в дереве. Каждое состояние считается за . Поэтому суммарная сложность времени и памяти препроцессинга — .Ответы на запросы
Ответы на запросы будут происходить за время
. Для ответа на запрос заметим сначала, что если , для некоторых и , то . Поэтому если , то пройдем от вершины на шагов вверх, это и будет новое значение и это можно сделать за . Можно записать число в двоичной системе, это представление этого число в виде суммы степеней двоек, и для всех пройти вверх последовательно из вершины в .Дальше считаем, что
.Если
, то ответ на запрос .А если
, то найдем такие вершины и , такие что , — предок , — предок и . Тогда ответом на запрос будет .Научимся находить эти вершины
и . Для этого сначала инициализируем и . Дальше на каждом шаге находим такое максимальное , что . И проходим из вершин и на шагов вверх. Если такого найти нельзя, то значения и , это те самые вершины, которые нам требуется найти, ведь .Оценим время работы. Заметим, что найденные
строго убывают. Во-первых, потому что мы находим на каждом шаге максимальное значение , а во-вторых, два раза подряд мы одно и то же получить не можем, так как тогда получилось бы, что можно пройти шагов, а значит вместо первого , мы бы нашли . А, значит, всего значений , их можно перебирать в порядке убывания. Сложность ответа на запрос .Псевдокод
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[u] - d[v]
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]