Изменения

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

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

583 байта добавлено, 07:41, 25 марта 2011
Нет описания правки
3) Построим дерево отрезков по полученному массиву.
=== Запрос ===
 
 
== Сложность ==
=== Препроцессинг ===
Длина массива глубин будет равна <tex>(2 * n - 1),</tex> т.е. дерево отрезков будет построено за <tex>O(n).</tex> Таким образом, препроцессинг работает за <tex>O(n).</tex>
=== Запрос ===
Время выполнения запроса равно времени запроса минимального элемента на отрезке в дереве отрезков, т.е. <tex>O(log n).</tex>
== См.также ==
Анонимный участник

Навигация