Изменения

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

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

12 байт убрано, 21:27, 15 мая 2011
м
Пример
== Пример ==
[[Файл:Lca to rmq.png|thumb|right|рис. 1]]<div>Рассмотрим дерево на рисунке 1. Найдем наименьшего общего предка вершин, помеченных красным цветом.
Список глубин, получающийся в результате обхода в глубину - <tex>[0, 1, 2, 1, 2, 1, 0, 1, 0].</tex>
Глубина наименьшего общего предка красных вершин равна минимуму на отрезке <tex>[2, 1, 0, 1].</tex></div>[[Файл:Lca to rmq.png|thumb|left|рис. 1]]
<div style='clear:left;'></div>
205
правок

Навигация