Изменения

{{Шаблон:Задача|definition == Постановка задачи LCA ==Пусть дано корневое дерево <tex>T</tex>. На вход подаются запросы вида <tex>(u,\;v)</tex>, для каждого запроса требуется найти их наименьшего общего предка.}}

|id=lca_suf_tree|definition = '''Наименьшим общим предком ''' (англ. ''least common ancestor)''' ) двух узлов <tex>u, </tex> и <tex>v</tex> в корневом дереве <tex>T</tex> называется узел <tex>w,</tex> , который среди всех узлов, являющихся предками как узла <tex>u,</tex> , так и <tex>v,</tex> , имеет наибольшую глубину.

1) В каждом узле будет храниться глубина узла в корневом дереве Для каждой вершины <tex>T.</tex>определим глубину с помощью следующей рекурсивной формулы::<tex>\mathrm{depth}(u)= \begin{cases}0 & u = \mathrm{root}(T),\\\mathrm{depth}(v) + 1 & u = \mathrm{son}(v).

2) Запустим обход Вот таким образом будет выглядеть массив <tex>\mathtt{vtx}</tex> после обхода в глубину из корня, который будет строить список посещений узлов. Глубина текущей вершины добавляется в список при входе в эту вершину, а также после каждого возвращения из её сына: [[Файл:Полная персистентность.png‎ | мини | left | 500x300px| Пример массива <tex>\mathtt{vtx}</tex>]]<br clear="all">

Обозначим Будем считать, что <tex>I[u]\mathrm{rmq}(d,l,r)</tex> - функция, возвращающая все индексы ячеек возвращает индекс минимального элемента в списке глубин, в которых хранится глубина узла <tex>ud</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> Можно брать любое значение .=== Доказательство корректности алгоритма ==={{Теорема|statement=Наименьшему общему предку вершин <tex>I[u]., v</tex> Для определённости соответствует минимальная глубина на отрезке <tex>d[\mathtt{I}[u] , \le mathtt{I}[v].]</tex>. == Доказательство корректности алгоритма =|proof=Рассмотрим два узла <tex>u, v</tex> корневого дерева <tex>T</tex>. Пусть узел Рассмотрим отрезок <tex>wd[\mathtt{I}[u]..\mathtt{I}[v]]</tex> . Поскольку этот отрезок {{- наименьший общий предок узлов --}} путь из <tex>u, </tex> в <tex>v.</tex> Очевидно, что в поддереве с корнем он проходит через их наименьшего общего предка <tex>w</tex> узел (в дереве есть только один простой путь между вершинами), а следовательно минимум на отрезке никак не больше глубины <tex>w</tex> будет иметь наименьшую глубину.Осталось доказатьЗаметим, что для любых значений в момент добавления <tex>\mathtt{I}[u],\; I[v]\; \exists</tex> значение обход посещал поддерево с корнем <tex>I[w]</tex>, что выполняется неравенство . В момент добавления <tex>I[u] \le I[w] \le mathtt{I}[v]\;(*).</tex>Пусть вершина мы все еще в поддереве с корнем <tex>uw</tex> посещается раньше, чем вершина <tex>v.</tex> ТогдаЗначит, если вершина <tex>v</tex> не явлется потомком вершины и на отрезке между <tex>\mathtt{I}[u,]</tex> будет выполняться неравенство и <tex>\;(*)mathtt{I}[v]</tex> (так как после посещения мы находились внутри поддерева, содержащего вершину с корнем <tex>uw</tex>. Отсюда сделаем заключение, в список будет добавлена что на рассматриваемом отрезке не посещалась вершина , отличная от <tex>w</tex>, а после - вершина с глубиной меньшей либо равной глубины <tex>vw</tex>), т. к. А если вершина <tex>u</tex> является предком подобной вершины нет в поддереве с корнем <tex>v,</tex> то вершина <tex>u</tex> будет наименьшим общим предком вершин <tex>u, vw</tex>. Очевидно, что неравенство выполняется}}.

Список глубин, получающийся в результате обхода в глубину {{- --}} <tex>[0, 1, 2, 1, 2, 1, 0, 1, 0].</tex>

[[Файл:Lca to rmq.png(2).png|thumb|leftcenter|рис. 1400x200px|Рисунок к примеру]]

 Для нахождения минимального элемента на отрезке можно использовать дерево отрезков. Длина массива глубин будет равна [[Алгоритм Фарака-Колтона и Бендера|алгоритм Фарака-Колтона и Бендера]] для <tex>(2n - 1),\pm 1RMQ</tex> , т.ек. соседние элементы в списке глубин отличаются не более чем на единицу. дерево отрезков будет построено за Длина списка глубин составляет <tex>O(n2n - 1).</tex> Таким , таким образом, препроцессинг работает за <tex>O(n).</tex> . Время выполнения запроса равно времени запроса минимального элемента на отрезке в дереве отрезков, т.е. {{---}} <tex>O(\log n1).</tex>.

== Ссылки Источники информации ==