Лекция 8. LCA, RMQ

Задача RMQ
Range Minimum (Maximum) Query
Static & dynamic, offline & online
Предподсчёт

Решение RMQ через Sparse table
Sparse Table – это таблица ST[][] такая, что ST[k][i] есть минимум на полуинтервале [A[i], A[i+2^k]).

Решение RMQ через дерево отрезков
Строим дерево отрезков
Фундаментальный отрезок -- полностью лежит в поддереве какой-то вершины
За указатель l -- если мы находимся в правом поддереве, то обновляем результат, поднимаемся и перескакиваем на своего правого соседа на уровне. Если находимся в левом поддереве -- просто поднимаемся и обновляем.
За указатель r -- если мы находимся в левом поддереве, то --\--
online

LCA. Метод двоичного подъёма
Наименьший общий предок двух вершин
dp[v][i] — номер вершины, в которую мы придём если пройдём из вершины v вверх по подвешенному дереву 2^i шагов, причём если мы пришли в корень, то мы там и останемся.

Сведение LCA к RMQ