Метод двоичного подъёма — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Модификация предподсчета за O(n))
(Модификация предподсчета за O(n) времени и O(n) памяти)
Строка 54: Строка 54:
 
</code>
 
</code>
  
==Модификация предподсчета за O(n) времени и O(n) памяти==
+
==Модификация предподсчета за <tex>O(n)</tex> времени и <tex>O(n)</tex> памяти==
  
Воспользуемся идеей Heavy-light декомпозиции, которая разбивает все вершины дерева на пути с одним важным свойством: поднимаясь от любой вершины до корня дерева придется сменить не более log(n) различных путей.
+
Воспользуемся идеей [[Heavy-light декомпозиция|Heavy-light декомпозиции]], которая разбивает все вершины дерева на вершинно непересекающиеся пути так, что поднимаясь от любой вершины до корня дерева придется сменить не более <tex>\log(n)</tex> различных путей.
  
Для каждой вершины будем хранить следующие значения:
+
===Препроцессинг===
1) расстояние до корня дерева
+
Построим декомпозицию, для каждой вершины, помимо ее предка  будем хранить дополнительно следующие значения:
2) количество потомков
+
# Расстояние до корня дерева.
3) предок (начало пути, на котором лежит вершина)
+
# Номер предка. (Начало пути от корня, ведущего в вершину).
4) номер вершины, в которую выходит ребро из предка, ведущее в нашу вершину.  
+
# Номер вершины, в которую выходит ребро из предка, ведущее в вершину.  
  
Все эти значения можно посчитать при построении декомпозиции.
+
===Вычисление LCA===
 +
Будем рекурсивно подниматься в направлении корня. Пусть на данной итерации рассматриваем вершины <tex>U</tex>, <tex>V</tex>. Сравним вершины (<tex>A</tex>, <tex>B</tex>), в которые идут ребра из предков рассматриваемых вершин.
 +
* <tex>A</tex> = <tex>B</tex>. Или <tex>U</tex> лежит на пути от корня к <tex>V</tex>, или наоборот. За LCA выберем ту вершину, которая лежит ближе к корню.
 +
* <tex>A</tex> <tex>\not=</tex> <tex>B</tex>. Нужно приблизить одну из вершин к корню, выбрав вместо нее её предка. Приближать будем на основании того, какая из вершин останется дальше от корня, после приближения.
  
Перейдем к вычислению LCA:
+
Очевидно, что в результате придем или в одну и ту же вершину, или одна из вершин окажется на пути от корня к другой. Тем самым мы найдем LCA.
Будем рекурсивно подниматься в направлении корня. Пусть на данной итерации рассматриваем вершины U, V. Сначала сравним вершины, в которые идут ребра из предков этих вершин. Если они совпадают, то, очевидно, или U лежит на пути от V к корню, или V лежит на пути от U к корню. Значит одна из них и является искомой. Выберем ту, чье расстояние до корня минимально.
 
 
 
Иначе нужно приблизить одну из этих вершин к корню, выбрав вместо нее ее предка. Приближать будем на основании того, какая из вершин останется дальше от корня, после приближения.
 
 
 
Очевидно, что в результате придем или в одну и ту же вершину, или одна из вершин окажется на пути ток корня к другой. Тем самым мы найдем LCA.
 
  
 
==Ассимптотика==
 
==Ассимптотика==

Версия 19:55, 7 мая 2016

Метод двоичного подъема — один из самых простых методов для решения задачи 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.

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

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

См. также

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