Изменения

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

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

36 байт добавлено, 11:48, 4 июня 2015
м
Запрос
=== Запрос ===
Будем считать, что <tex>\mathrm{rmq}(d,l,r)</tex> возвращает индекс минимального элемента в <tex>d</tex> на отрезке <tex>[l..r]</tex>. Тогда ответом на запрос <tex>\mathrm{lca}(u, v)</tex>, где <tex>I[u] \le \mathtt{I}[v]</tex>, будет <tex>\mathtt{vtx}[\mathrm{rmq}(d,\mathtt{I}[u], \mathtt{I}[v])]</tex>.
=== Доказательство корректности алгоритма ===
74
правки

Навигация