Метод двоичного подъёма

Метод двоичного подъема — один из самых простых методов для решения задачи LCA в online. Он не использует метод решение задачи RMQ и основан на методе динамического программирования.

Описание алгоритма

Как и большинство on-line алгоритмов для решения задачи LCA, этот метод делает сначала препроцессинг, чтобы потом отвечать на запросы.

Препроцессинг

Препроцессинг заключается в том, чтобы посчитать функцию: [math] dp[v][i] [/math] — номер вершины, в которую мы придем если пройдем из вершины [math] v [/math] вверх по подвешенному дереву [math] 2 ^ i [/math] шагов, причем если мы пришли в корень, то мы там и останемся. Для этого сначала обойдем дерево в глубину и для каждой вершины запишем номер ее родителя [math] p[v] [/math] и глубину вершины в подвешенном дереве [math] d[v] [/math]. Если [math] v [/math] — корень, то [math] p[v] = v [/math]. Тогда для функции [math] dp [/math] есть рекуррентная формула:

[math]dp[v][i]= \begin{cases} p[v] & i = 0,\\ dp[dp[v][i - 1]][i - 1] & i \: \textgreater \: 0. \end{cases}[/math]

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

Всего состояний динамики [math] O(n \log{n})[/math], где [math] n [/math] — это количество вершин в дереве. Каждое состояние считается за [math] O(1) [/math]. Поэтому суммарная сложность времени и памяти препроцессинга — [math] O(n \log{n}) [/math].

Ответы на запросы

Ответы на запросы будут происходить за время [math] O(\log{n})[/math]. Для ответа на запрос заметим сначала, что если [math] c = LCA(v, u) [/math], для некоторых [math] v [/math] и [math] u [/math], то [math] d[c] \leqslant \min(d[v], d[u])[/math]. Поэтому если [math] d[v] \lt d[u] [/math], то пройдем от вершины [math] u [/math] на [math] (d[u] - d[v]) [/math] шагов вверх, это и будет новое значение [math] u [/math] и это можно сделать за [math] O(\log{n}) [/math]. Можно записать число [math] (d[u] - d[v]) [/math] в двоичной системе, это представление этого число в виде суммы степеней двоек, [math] 2 ^ {i_1} + 2 ^ {i_2} + \ldots + 2 ^ {i_l} [/math] и для всех [math] i_j[/math] пройти вверх последовательно из вершины [math] u [/math] в [math] dp[u][i_j] [/math].

Дальше считаем, что [math] d[v] = d[u] [/math].

Если [math] v = u [/math], то ответ на запрос [math] v [/math].

А если [math] v \neq u [/math], то найдем такие вершины [math] x [/math] и [math] y [/math], такие что [math] x \neq y [/math], [math] x [/math] — предок [math] v [/math], [math] y [/math] — предок [math] u [/math] и [math] p[x] = p[y] [/math]. Тогда ответом на запрос будет [math] p[x] [/math].

Научимся находить эти вершины [math] x [/math] и [math] y [/math]. Для этого сначала инициализируем [math] x = v [/math] и [math] y = u [/math]. Дальше на каждом шаге находим такое максимальное [math] k [/math], что [math] dp[x][k] \neq dp[y][k] [/math]. И проходим из вершин [math] x [/math] и [math] y [/math] на [math] 2 ^ k [/math] шагов вверх. Если такого [math] k [/math] найти нельзя, то значения [math] x [/math] и [math] y [/math], это те самые вершины, которые нам требуется найти, ведь [math] p[x] = dp[x][0] = dp[y][0] = p[y] [/math].

Оценим время работы. Заметим, что найденные [math] k [/math] строго убывают. Во-первых, потому что мы находим на каждом шаге максимальное значение [math] k [/math], а во-вторых, два раза подряд мы одно и то же [math] k [/math] получить не можем, так как тогда получилось бы, что можно пройти [math] 2 ^ k + 2 ^ k = 2 ^ {k + 1}[/math] шагов, а значит вместо первого [math] k [/math], мы бы нашли [math] k + 1 [/math]. А, значит, всего [math] O(\log{n}) [/math] значений [math] k [/math], их можно перебирать в порядке убывания. Сложность ответа на запрос [math] O(\log{n}) [/math].

Псевдокод

  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] [math]\geqslant 2 ^ i [/math]
           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]

Модификация предподсчета за [math]O(n)[/math] времени и [math]O(n)[/math] памяти

Воспользуемся идеей Heavy-light декомпозиции, которая разбивает все вершины дерева на вершинно непересекающиеся пути так, что поднимаясь от любой вершины до корня дерева придется сменить не более [math]\log(n)[/math] различных путей.

Препроцессинг

Построим декомпозицию, для каждой вершины, помимо ее предка будем хранить дополнительно следующие значения:

1. Расстояние до корня дерева.
2. Номер предка. (Начало пути от корня, ведущего в вершину).
3. Номер вершины, в которую выходит ребро из предка, ведущее в вершину.

Вычисление LCA

Будем рекурсивно подниматься в направлении корня. Пусть на данной итерации рассматриваем вершины [math]U[/math], [math]V[/math]. Сравним вершины ([math]A[/math], [math]B[/math]), в которые идут ребра из предков рассматриваемых вершин.

• [math]A[/math] = [math]B[/math]. Или [math]U[/math] лежит на пути от корня к [math]V[/math], или наоборот. За LCA выберем ту вершину, которая лежит ближе к корню.
• [math]A[/math] [math]\not=[/math] [math]B[/math]. Нужно приблизить одну из вершин к корню, выбрав вместо нее её предка. Приближать будем на основании того, какая из вершин останется дальше от корня, после приближения.

Очевидно, что в результате придем или в одну и ту же вершину, или одна из вершин окажется на пути от корня к другой. Тем самым мы найдем LCA.

Псевдокод

 # Находит наименьшего общего предка вершин u и v
 def lca(int u, int v):
   # Проверяем вершины, в которые идут ребра из предков.
   if (turn[u] == turn[v]):
     # Ответ найден, выберем ближайшую к корню.
     if (dist[u] < dist[v]):
       return u
     else:
       return v
   # Приблизимся к корню. Выбираем наиболее удаленную вершину.
   if (dist[last[u]] > dist[last[v]]):
     return lca(last[u], v)
   return lca(last[v], u)

Ассимптотика

• Память: Для реализации алгоритма требуется [math]O(n)[/math] памяти.
• Препроцессинг: Heavy-light декомпозиция строится за [math]O(n)[/math].
• Запросы: По свойству heavy-light декомпозиции, на пути от вершины к корню мы сменим не более [math]log(n)[/math] путей. Значит время выполнения запроса также [math]O(log(n))[/math].

См. также

• Сведение задачи LCA к задаче RMQ

Источники информации

• Wikipedia: LCA
• TopCoder tutorial: RMQ and LCA
• MAXimal :: algo :: Метод двоичного подъема
• Habrahabr: Алгоритм поиска наименьшего общего предка в дереве