Изменения

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

Сведение задачи LCA к задаче RMQ

9 байт добавлено, 11:46, 4 июня 2015
м
Препроцессинг
#Cписок глубин посещенных вершин <tex>d</tex>. Глубина текущей вершины добавляется в конец списка при входе в данную вершину, а также после каждого возвращения из её сына.
#Список посещений узлов <tex>vtx</tex>, строящийся аналогично предыдущему, только добавляется не глубина а сама вершина.
#Значение функции <tex>\mathtt{I}[u]</tex>, возвращающей любой индекс в списке глубин <tex>d</tex>, по которому была записана глубина вершины <tex>u</tex> (например на момент входа в вершину).
=== Запрос ===
74
правки

Навигация