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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Модификация предподсчета за O(n) времени и O(n) памяти)
м (rollbackEdits.php mass rollback)
 
(не показано 12 промежуточных версий 7 участников)
Строка 1: Строка 1:
'''Метод двоичного подъема''' {{---}} один из самых простых методов для решения задачи [[Сведение задачи LCA к задаче RMQ|LCA]] в online. Он не использует метод решение задачи '''RMQ''' и основан на методе [[Динамическое программирование | динамического программирования]].
+
'''Метод двоичного подъёма''' {{---}} один из самых простых методов для решения задачи [[Сведение задачи LCA к задаче RMQ|LCA]] в online. Он не использует метод решения задачи '''RMQ''' и основан на методе [[Динамическое программирование | динамического программирования]].
 
==Описание алгоритма==
 
==Описание алгоритма==
 
Как и большинство '''on-line''' алгоритмов для решения задачи [[Сведение задачи LCA к задаче RMQ|LCA]], этот метод делает сначала препроцессинг, чтобы потом отвечать на запросы.
 
Как и большинство '''on-line''' алгоритмов для решения задачи [[Сведение задачи LCA к задаче RMQ|LCA]], этот метод делает сначала препроцессинг, чтобы потом отвечать на запросы.
 
===Препроцессинг===
 
===Препроцессинг===
Препроцессинг заключается в том, чтобы посчитать функцию: <tex> dp[v][i] </tex> {{---}} номер вершины, в которую мы придем если пройдем из вершины <tex> v </tex> вверх по подвешенному дереву <tex> 2 ^ i </tex> шагов, причем если мы пришли в корень, то мы там и останемся.
+
Препроцессинг заключается в том, чтобы посчитать функцию: <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> есть рекуррентная формула:
+
Для этого сначала обойдем дерево в глубину, и для каждой вершины запишем номер её родителя <tex> p[v] </tex> и глубину вершины в подвешенном дереве <tex> d[v] </tex>. Если <tex> v </tex> {{---}} корень, то <tex> p[v] = v </tex>. Тогда для функции <tex> dp </tex> есть рекуррентная формула:
  
 
<tex>dp[v][i]= \begin{cases}
 
<tex>dp[v][i]= \begin{cases}
 
p[v] & i = 0,\\
 
p[v] & i = 0,\\
dp[dp[v][i - 1]][i - 1] & i \: \textgreater \: 0.
+
dp[dp[v][i - 1]][i - 1] & i \: > \: 0.
 
\end{cases}</tex>
 
\end{cases}</tex>
  
Строка 17: Строка 17:
 
===Ответы на запросы===
 
===Ответы на запросы===
 
Ответы на запросы будут происходить за время <tex> O(\log{n})</tex>.
 
Ответы на запросы будут происходить за время <tex> O(\log{n})</tex>.
Для ответа на запрос заметим сначала, что если <tex> c = LCA(v, u) </tex>, для некоторых <tex> v </tex> и <tex> u </tex>, то <tex> d[c] \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> i_j</tex> пройти вверх последовательно из вершины <tex> u </tex> в <tex> dp[u][i_j] </tex>.
+
Для ответа на запрос заметим сначала, что если <tex> c = LCA(v, u) </tex>, для некоторых <tex> v </tex> и <tex> u </tex>, то <tex> d[c] \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> i_j</tex> пройти вверх последовательно из вершины <tex> u </tex> в <tex> dp[u][i_j] </tex>.
  
 
Дальше считаем, что <tex> d[v] = d[u] </tex>.  
 
Дальше считаем, что <tex> d[v] = d[u] </tex>.  
Строка 23: Строка 23:
 
Если <tex> v = u </tex>, то ответ на запрос <tex> v </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> 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> 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>.
Строка 30: Строка 30:
  
 
==Псевдокод==
 
==Псевдокод==
<code>
 
 
   '''function''' preprocess():
 
   '''function''' preprocess():
 
       '''int[]''' p = dfs(0)
 
       '''int[]''' p = dfs(0)
Строка 43: Строка 42:
 
         swap(v, u)
 
         swap(v, u)
 
       '''for''' i = log(n) '''downto''' 0
 
       '''for''' i = log(n) '''downto''' 0
         '''if''' d[u] - d[v] <tex>\geqslant 2 ^ i </tex>
+
         '''if''' d[dp[u][i]] - d[v] >= 0
 
             u = dp[u][i]
 
             u = dp[u][i]
 
       '''if''' v == u
 
       '''if''' v == u
Строка 52: Строка 51:
 
             u = dp[u][i]
 
             u = dp[u][i]
 
       '''return''' p[v]
 
       '''return''' p[v]
</code>
 
  
 
==См. также==
 
==См. также==
Строка 60: Строка 58:
 
* [http://en.wikipedia.org/wiki/Lowest_common_ancestor Wikipedia: LCA]
 
* [http://en.wikipedia.org/wiki/Lowest_common_ancestor Wikipedia: LCA]
 
* [http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor TopCoder tutorial: RMQ and LCA]
 
* [http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor TopCoder tutorial: RMQ and LCA]
* [http://e-maxx.ru/algo/lca_simpler MAXimal :: algo :: Метод двоичного подъема ]
+
* [http://e-maxx.ru/algo/lca_simpler MAXimal :: algo :: Метод двоичного подъёма ]
* [https://habrahabr.ru/post/198464 Habrahabr: Алгоритм поиска наименьшего общего предка в дереве ]
 
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Задача о наименьшем общем предке]]
 
[[Категория: Задача о наименьшем общем предке]]

Текущая версия на 19:39, 4 сентября 2022

Метод двоичного подъёма — один из самых простых методов для решения задачи 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 \: \gt \: 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[dp[u][i]] - d[v] >= 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]

См. также

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