74
правки
Изменения
→Алгоритм
== Алгоритм ==
=== Идея ===
Будем решать задачу LCA, уже умея решать задачу RMQ. Тогда поиск наименьшего общего предка <tex>i</tex>-того и <tex>j</tex>-того элементов сводится к запросу минимума на отрезке массива, который будет введен позднее.
=== Препроцессинг ===
Для каждой вершины <tex>T</tex> определим глубину с помощью следующей рекурсивной формулы:
