1632
правки
Изменения
м
rollbackEdits.php mass rollback
#Значение функции <tex>\mathtt{I}[u]</tex>, возвращающей индекс в списке глубин <tex>d</tex>, по которому была записана глубина вершины <tex>u</tex> (например на момент входа в вершину).
Вот таким образом будет будут выглядеть массив <tex>\mathtt{vtx}</tex> эти три массива после обхода в глубину:
[[Файл:Полная персистентностьHoD8KSiOzTg.png jpg | мини | left | 500x200px700x500px| Пример массива <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>.
=== Доказательство корректности алгоритма ===
{{Теорема
