Изменения

Перейти к: навигация, поиск

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

13 байт убрано, 17:52, 28 июня 2011
м
Нет описания правки
'''Метод двоичного подъема''' {{---}} это один из самых простых методов для решения задачи [[Сведение задачи LCA к задаче RMQ|LCA]] в on-line и он . Он не использует метод решение задачи '''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}
53
правки

Навигация