Користувач:Qwertyazaza

Метод двійкового підйому — один з методів для вирішення задачі LCA в online. Він не використовує RMQ і заснований на методі динамічного програмування.

Опис алгоритму

Як і більшість online алгоритмів, цей метод спочатку робить підрахунок offline, а потім це використовує для відповіді на запити.

Підрахунок offline

Підрахунок offline полягає в тому, щоб порахувати функцію : $dp[v][i]$ — вершина, у яку ми прийдемо, пройшовши уверх $2^{i}$ребер з вершини $v$ , при чому, якщо ми прийшли в корінь дерева, то ми там і залишаємося. Для цього спочатку запустимо обхід в глибину з кореня і для кожної вершини запишемо номер її батька $p[v]$ та глибину вершини в підвішеному дереві $d[v]$. Якщо корінь — $v$,

то — $p[v]=v$, тоді для функції $dp$ є рекурентна формула :

$dp[v][i]={\begin{cases}p[v],&i=0,\\dp[dp[v][i-1]][i-1],&i>0.\end{cases}}$

Для того, щоб відповідати на запити, нам потрібні тільки ті значення $dp[v][i]$, для яких $i\leq \log _{2}(n)$, бо для великих значень $i\ \ dp[v][i]$ дорівнюватиме значенню кореня.

Всього станів динаміки $O(nlog(n))$, де $n$кількість вершин у дереві. Кожний стан рахується за $O(1)$, тому загальна складність $O(nlog(n))$.

Відповіді на запити

Відповідати на запити будемо за час $O(log(n))$. Спочатку помітимо, що якщо вершина $c=LCA(u,v)$для деяких $u$та $v$ то $d[c]\leq \min(d[u],d[v])$. Тому, якщо $d[u]>d[v]$, то пройдемо від вершини $u$на $(d[u]-d[v])$кроків уверх, це і буде нове значення $u$, яке ми можемо порахувати за $O(log(n))$. Число $(d[u]-d[v])$ми можемо записати у двійковій системі числення як :

$2^{i_{1}}+2^{i_{2}}+...2^{i_{l}}$і для всіх $i_{j}$пройти вверх послідовно із вершини $u$ у вершину $dp[u][i_{j}]$.

Далі вважаємо, що $d[v]=d[u]$.

Якщо $v=u$, то відповідь на запит $v$.

Інакше, якщо $v\neq u$, то знайдемо такі вершини $x$та $y$, що $x\neq y$та $p[x]=p[y]$. Тоді відповіддю на запит буде $p[x]$.

Щоб знайти вершини $x$та $y$, спочатку ініціалізуємо $x=v$та $y=u$, та знаходитимемо таке максимальне $k$, що $dp[x][k]\neq dp[y][k]$. Тоді піднімемося вгору на $2^{k}$кроків угору з обидвох вершин, та повторимо цю процедуру. Якщо такого $k$знайти не можна, то знайдені вершини і є тими, які нам потрібно знайти, бо $p[x]=dp[x][0]=dp[y][0]=p[y]$.

Оцінимо час роботи алгоритму.

Помітимо, що знайдені $k$строго спадають, оскільки, по-перше, щоразу ми знаходимо максимальне значення $k$, а по-друге, два рази поспіль одне й те саме значення $k$отримати не можемо, бо $2^{k}+2^{k}=2^{k+1}$і ми тоді б взяли $k+1$, тому можна перебирати всього $O(log(n))$значень $k$ в порядку спадання. Отже, складність відповіді $O(log(n))$.

Псевдокод

  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]