24
правки
Изменения
м
==Модификация предподсчета за <tex>O(n)</tex> времени и <tex>O(n)</tex> памяти==
Воспользуемся идеей [[Heavy-light декомпозиция|Heavy-light декомпозиции]], которая разбивает все вершины дерева на вершинно непересекающиеся пути так, что поднимаясь от любой вершины до корня дерева придется сменить не более <tex>\log(n)</tex> различных путей.
===Препроцессинг===
Построим декомпозицию, для каждой вершины, помимо ее предка будем хранить дополнительно следующие значения:
# Расстояние до корня дерева.
# Номер предка. (Начало пути от корня, ведущего в вершину).
# Номер вершины, в которую выходит ребро из предка, ведущее в вершину.
===Вычисление 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.
===Реализация===
===Ассимптотика===
* '''Память''': Для реализации алгоритма требуется <tex>O(n)</tex> памяти.
* '''Препроцессинг''': Heavy-light декомпозиция строится за <tex>O(n)</tex>.
* '''Запросы''': По свойству heavy-light декомпозиции, на пути от вершины к корню мы сменим не более <tex>log(n)</tex> путей. Значит время выполнения запроса также <tex>O(log(n))</tex>.
Правка пунктуации
'''Метод двоичного подъемаподъёма''' {{---}} один из самых простых методов для решения задачи [[Сведение задачи LCA к задаче RMQ|LCA]] в online. Он не использует метод решение решения задачи '''RMQ''' и основан на методе [[Динамическое программирование | динамического программирования]].
==Описание алгоритма==
Как и большинство '''on-line''' алгоритмов для решения задачи [[Сведение задачи LCA к задаче RMQ|LCA]], этот метод делает сначала препроцессинг, чтобы потом отвечать на запросы.
===Препроцессинг===
Препроцессинг заключается в том, чтобы посчитать функцию: <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>dp[v][i]= \begin{cases}
p[v] & i = 0,\\
dp[dp[v][i - 1]][i - 1] & i \: \textgreater > \: 0.
\end{cases}</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> d[v] = d[u] </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> 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>.
'''return''' p[v]
</code>
==См. также==
* [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://e-maxx.ru/algo/lca_simpler MAXimal :: algo :: Метод двоичного подъема подъёма ]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Задача о наименьшем общем предке]]
