Изменения

Запустим [[Обход в глубину, цвета вершин|обход в глубину]] из корня, который будет строить список посещений узлов вычислять значения следующих величин: #Cписок глубин посещенных вершин <tex>d</tex>. Глубина текущей вершины добавляется в конец списка при входе в данную вершину, а также после каждого возвращения из её сына.#Список посещений узлов <tex>vtx</tex>, строящийся аналогично предыдущему, только добавляется не глубина а сама вершина.#Значение функции <tex>I[u]</tex>, возвращающей любой индекс в списке глубин <tex>d</tex>, по которому была записана глубина вершины <tex>u</tex> (например при входе в вершину).

Обозначим Будем считать, что <tex>I[u]</tex> {\mathrm{---rmq}} функция(d, l, возвращающая любой индекс ячейки в списке глубин <tex>depthr)</tex>, возвращает индекс минимального элемента в котором хранится глубина узла <tex>ud</tex>. Ее можно строить во время обхода в глубину.Пусть имеется запрос {{---}} пара узлов на отрезке <tex>u, v[l..r]</tex> В результате обхода в глубину получился список глубин вершин, в котором наименьшему общему предку вершин . Тогда ответом на запрос <tex>\mathrm{lca}(u, v)</tex> соответствует минимальная глубина на отрезке будет <tex>depth\mathrm{vtx}[\mathrm{rmq}(d, I[u], I[v])]</tex>.