Изменения
Нет описания правки
{{В разработке}}
'''Метод двоичного подъема ''' {{---}} это один из самых простых методов для решения задачи [[Сведение задачи LCA к задаче RMQ|LCA]] в on-line и он не использует метод решение задачи '''RMQ'''. Он основан на методе динамического программирования.
==Описание алгоритма==
Как и все '''on-line ''' алгоритмы, этот метод делает сначала препроцессинг, чтобы потом отвечать на запросы.
===Препроцессинг===
Препроцессинг заключается в том, чтобы посчитать функцию: <tex> dp[v][i] </tex> {{---}} это номер вершины, в которую мы придем если пройдем из вершины <tex> v </tex> вверх по подвешенному дереву <tex> 2 ^ i </tex> шагов, причем если мы пришли в корень, то мы там и останемся.
