Изменения

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

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

297 байт добавлено, 13:02, 9 июня 2015
Препроцессинг
#Cписок глубин посещенных вершин <tex>d</tex>. Глубина текущей вершины добавляется в конец списка при входе в данную вершину, а также после каждого возвращения из её сына.
#Список посещений узлов <tex>\mathtt{vtx}</tex>, строящийся аналогично предыдущему, только добавляется не глубина а сама вершина.
#Значение функции <tex>\mathtt{I}[u]</tex>, возвращающей любой индекс в списке глубин <tex>d</tex>, по которому была записана глубина вершины <tex>u</tex> (например на момент входа в вершину). Вот таким образом будет выглядеть массив <tex>\mathtt{vtx}</tex> после обхода в глубину: [[Файл:Полная персистентность.png‎ | мини | left | 500x300px| Пример массива <tex>\mathtt{vtx}</tex>]]<br clear="all">
=== Запрос ===
Будем считать, что <tex>\mathrm{rmq}(d,l,r)</tex> возвращает индекс минимального элемента в <tex>d</tex> на отрезке <tex>[l..r]</tex>. Тогда ответом на запрос <tex>\mathrm{lca}(u, v)</tex>, где <tex>\mathtt{I}[u] \leqslant \mathtt{I}[v]</tex>, будет <tex>\mathtt{vtx}[\mathrm{rmq}(d,\mathtt{I}[u], \mathtt{I}[v])]</tex>.
 
=== Доказательство корректности алгоритма ===
{{Теорема
Список глубин, получающийся в результате обхода в глубину {{---}} <tex>[0, 1, 2, 1, 2, 1, 0, 1, 0].</tex>
Глубина наименьшего общего предка красных вершин равна минимуму на отрезке <tex>[2, 1, 0, 1].</tex>
[[Файл:Lca to rmq.png(2).png|thumb|center|300x150px400x200px|Рисунок к примеру]]
<div style='clear:left;'></div>
74
правки

Навигация