Изменения

Сначала научимся выполнять эти операции для частного случаярассмотрим частный случай, в котором все деревья {{--- }} это пути, и мы хотим уметь: [[Файл:Path_to_tree.png|250px|thumb|right|Пример построения дерева для пути]]* прибавлять константу и искать минимум на некотором суффиксе (то есть на пути от вершины до корня), * разбить один путь на два,* подвешивать голову одного пути к хвосту другого.  Если бы не последние две операции, то можно было бы применить [[Дерево отрезков. Построение|дерево отрезков]], сложив в него вершины в том порядке в котором они идут в пути. Но непонятно, как сливать или разрезать деревья отрезков. Если использовать какие-нибудь сливаемые деревья, то <tex>link</tex> и <tex>cut</tex> реализуются просто, осталось научиться искать минимум и прибавлять константу на пути. Для этого представим путь , как и в деревьях отрезков, будем хранить дополнительные значения в виде вершинах.В качестве сливаемых деревьев выберем [[Splay-дерево|splay-деревадеревья]], в котором которых ключи выбираются равными глубине вершины. [[Файл:Path_to_tree.png|250px|thumb|right|Пример построения дерева для пути]]