Изменения

'''Link-cut treeДинамические деревья''' (англ.''dynamic tree'') используются в двух областях: [[Определение сети, потока|потоки]] и динамические графы.В первом случае динамические деревья позволяют построить эффективные алгоритмы для задачи о поиске максимального потока.В динамическом графе периодически происходят изменения: появляются и исчезают ребра, меняются их веса. Нужно быстро обрабатывать изменения, а также уметь [[Отношение связности, компоненты связности | проверять связность]], [[Алгоритмы на деревьях|искать диаметр]]. Динамические деревья являются инструментом, который позволяет легко решать эти задачи. Динамические деревья особенно эффективны, когда нужно работать с большими деревьями и большим количеством запросов '''link''' и '''cut'''. '''Link-cut tree''' {{---}} это структура данных, которая хранит [[Дерево, эквивалентные определения |лес деревьев ]] и позволяет выполнять следующие операции:* '''<tex>\mathrm{min(v)}</tex>''' {{---}} искать минимум на пути от вершины до корня;,* '''<tex>\mathrm{add(v, c)}</tex>''' {{---}} прибавлять константу на пути от вершины до корня;,* '''<tex>\mathrm{link(u, w)}</tex>''' {{---}} подвешивать одно дерево на другое;,* '''<tex>\mathrm{cut(v)}</tex>''' {{---}} отрезать дерево с корнем в вершине <tex>\mathrm{v}</tex>.

* '''<tex>\mathrm{add(v, c)}</tex>''' и '''<tex>\mathrm{min(v)}</tex>''' {{---}} прибавлять константу и искать минимум на некотором суффиксе (то есть на пути от вершины до корня), * '''<tex>\mathrm{cut(v)}</tex>''' {{---}} разбить один путь на два,* '''<tex>\mathrm{link(v, u)}</tex>''' {{---}} подвешивать голову одного пути к хвосту другого.

Если бы не последние две операции, то можно было бы применить [[Несогласованные поддеревья. Реализация массового обновления|дерево отрезков]], сложив в него вершины в том порядке в котором они идут в пути. Но непонятно, как сливать или разрезать деревья отрезков. Если Эту задачу можно решить при помощи [[Декартово дерево по неявному ключу|декартового дерева по неявному ключу]]. Также, если использовать какие-нибудь сливаемые деревья, то <tex>\mathrm{link}</tex> и <tex> \mathrm{cut}</tex> реализуются просто. Осталось научиться искать минимум и прибавлять константу на пути. Для этого, как и в деревьях отрезков, будем хранить дополнительные значения в вершинах.

Чтобы обобщить, разобьем дерево на множество непересекающихся путей. Каждое ребро обозначим либо solid-ребромсплошным, либо dashed-ребромпунктирным. Все пути в link-cut дереве хранятся в виде splay-деревьев. Корень каждого splay-дерева хранит указатель на вершину-родителя. В дальнейшем будем называть этот указатель <tex>pathparent</tex>.

Ключевая операция в link-cut-деревьях {{---}} <tex>\mathrm{expose(u)}</tex>. После её выполнения <tex>u</tex> лежит на одном пути с корнем link-cut дерева и при этом становится корнем в splay-дереве получившегося пути. Для этого она поднимается вверх по link-cut дереву, и если какой-нибудь путь пересекает путь от <tex>u</tex> до корня, то она его отрезает, разъединяя splay-дерево и делая соответствующее solid-сплошное ребро dashed-пунктирным ребром.

'''function''' expose(u : '''tree'''):

v <tex>\leftarrow=</tex> u

p <tex>\leftarrow=</tex> pathparent(v) <font color=green>//получаем указатель на ближайшую вершину пути, пересекающего путь от u до корня</font>

parent(right(p)) <tex>\leftarrow=</tex> null <font color=green>//поэтому правое поддерево p делаем новым путем</font> pathparent(right(p)) <tex>\leftarrow=</tex> p right(p) <tex>\leftarrow=</tex> v <font color=green>//объединяем оставшийся и построенный пути</font>

<tex>\vartriangle</tex>min(p) <tex>\leftarrow=</tex> min{0, <tex>\vartriangle</tex>min(left(p)) + <tex>\vartriangle</tex>w(left(p)), <tex>\vartriangle</tex>min(right(p)) + <tex>\vartriangle</tex>w(right(p))} pathparent(v) <tex>\leftarrow=</tex> null v <tex>\leftarrow=</tex> p

'''function''' add(v : '''tree''', c : '''int'''):

Построим splay-дерево для пути и сравним минимум вес корня <tex>v</tex> c минимумом в левом поддереве: '''intfunction''' min(v : '''tree'''):'''int'''

'''treefunction''' link(v : '''tree''', u : '''tree'''):'''tree'''

parent(u) <tex>\leftarrow=</tex> v <font color=green>// 2. обновляем <tex>\vartriangle</tex>w, <tex>\vartriangle</tex>min</font> left(v) <tex>\leftarrow=</tex> u <tex>\vartriangle</tex>min(v) <tex>\leftarrow=</tex> min{0, <tex>\vartriangle</tex>min(u) + <tex>\vartriangle</tex>w(u), <tex>\vartriangle</tex>min(right(v)) + <tex>\vartriangle</tex>w((right(v)))}

Отрезает дерево с корнем <tex>v</tex>. После вызова <tex>\mathrm{expose(v)}</tex> вершина <tex>v</tex> станет корнем splay-дерева, и в правом поддереве будут содержатся содержаться все вершины, которые были ниже <tex>v</tex> в link-cut дереве, а в левом {{---}} те что выше. Обнулив указатель на левого ребенка <tex>v</tex> и на родителя в левом поддереве, получим требуемое.

'''function''' cut(v : '''tree'''):

<tex>\vartriangle</tex>min(v) <tex>\leftarrow=</tex> min{0, <tex>\vartriangle</tex>min(right(v)) + <tex>\vartriangle</tex>w(right(v))} parent(left(v)) <tex>\leftarrow=</tex> null parent(left(v)) <tex>\leftarrow=</tex> null

Назовем ребро из <tex>u</tex> в её родителя <tex>v</tex> тяжелым, если количество детей <tex>u</tex> равное <tex>d(u) > \fracdfrac{1}{2} d(v)</tex>.

Операция <tex>u</tex> осуществляется с помощью последовательности преобразований dashed-пунктирного ребра в solid-сплошное ребро и другого solid-сплошного ребра в dashed-пунктирное ребро. Обозначим количество таких преобразований за <tex>M</tex>. Найдем количество преобразований сделанных в течение <tex>\mathrm{expose(u)}</tex>. Пусть <tex>H</tex> {{---}} множество всех тяжелых ребер, <tex>L</tex> {{---}} все легкие ребра, <tex>S \rightarrow D</tex> {{---}} множество solid-сплошных ребер, преобразованных в dashed пунктирные в течение одного <tex>\mathrm{expose}</tex>, <tex>D \rightarrow S</tex> {{---}} множество dashed-пунктирных ребер, преобразованных в solidсплошные.

По лемме, количество легких dashed-пунктирных ребер, преобразованных в solidсплошные, будет не больше, чем <tex>\log n</tex>.

Обозначим за <tex>F</tex> лес деревьев, в которых каждое ребро либо solidсплошное, либо dashedпунктирное, a <tex>F'</tex> {{---}} лес, получившийся из <tex>F</tex> после одного вызова <tex>\mathrm{expose}</tex>. Определим потенциал <tex>\Phi _{a}(F) = n - 1 - |\{H \cap solid-edges\}|</tex>, <tex>\Delta \Phi _{a}</tex> {{---}} увеличение <tex>\Phi _{a}</tex> после одной операции <tex>\mathrm{expose}</tex>.

Теперь проанализируем <tex>M</tex>. Используя тот факт, что начальное значение <tex>\Phi _{a}</tex> не превосходит <tex>n - 1</tex>, приходим к тому, что для деревьев с <tex>n</tex> вершинами, по крайней мере за <tex>n - 1</tex> операцию <tex>\mathrm{expose}</tex>, среднее <tex>M</tex> на одну операцию будет не больше, чем <tex>1 + 2\log n</tex>.

Докажем, что [[Амортизационный анализ|амортизационная стоимость операции ]] <tex>\mathrm{expose}</tex> равна <tex>O(\log n)</tex>.

Пусть <tex>s(v)</tex> {{---}} количество вершин в поддеревьях <tex>v</tex> ( здесь имеется в виду splay-дерево пути, котоый который строится в ходе выполнения <tex>\mathrm{expose}</tex>), <tex>r(v) = \log s(v)</tex>. По [[Splay-дерево#Lemma1|лемме]] стоимость ''i''-той операции <tex>\mathrm{splay}</tex> не превосходит <tex>1 + 3 \cdot (r(t) - r(v))</tex>. Это приводит к тому, что амортизационная стоимость <tex>\mathrm{expose}</tex> ограничена следующим значением:

Здесь <tex>M = O(\log n)</tex>, поэтому амортизационная стоимость <tex>\mathrm{expose}</tex> равна <tex>O(\log n)</tex>.

'''treefunction''' lca(u : '''tree''', v : '''tree'''):'''tree'''

*[[Метод двоичного подъема| Метод двоичного подъема]]*[[Алгоритм Тарьяна поиска LCA за O(1) в оффлайн | Алгоритм Тарьяна поиска LCA за O(1) в оффлайн]]*[[Алгоритм Шибера-Вишкина | Алгоритм Шибера-Вишкина]] 

*[http://www.lektorium.tv/lecture/14464 А.С. Станкевич, "Дополнительные главы алгоритмов, Link-cut trees"]*[https://sites.google.com/site/indy256/algo/link-cut-tree-lca Реализация LCA на link-cut дереве]*[http://www.cs.cmu.edu/~sleator/papers/dynamic-trees.pdf ''D. Sleator and R. Tarjan''. , "A Data Structure for Dynamic Trees"]*[http://compgeom.cs.uiuc.edu/~jeffe/teaching/datastructures/2006/notes/07-linkcut.pdf Jeff Erickson. Lecture 7. Link-Cut Trees]*[http://planarity.org/Klein_splay_trees_and_link-cut_trees.pdf Optimization Algorithms for Planar Graphs. Splay trees and link-cut trees]*[http://en.wikipedia.org/?title=wiki/Link/cut_tree Wikipedia {{---}} Link/cut tree]