Изменения

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

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

177 байт добавлено, 21:16, 15 мая 2011
м
Нет описания правки
=== Запрос ===
Пусть имеется запрос пара узлов <tex>u, v.</tex> Обозначим <tex>I[u]</tex> - индекс ячейки функция, возвращающая все индексы ячеек в списке глубин, в которой которых хранится глубина узла <tex>u.</tex>Пусть имеется запрос пара узлов <tex>u, v.</tex> В результате получился список глубин вершин, в котором наименьшему общему предку вершин <tex>u, v</tex> соответствует минимальная глубина на отрезке <tex>[I[u], I[v]].</tex> Можно брать любое значение <tex>I[u].</tex>Для определённости <tex>I[u] \le I[v].</tex>
== Доказательство корректности алгоритма ==
205
правок

Навигация