Изменения

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

Link-Cut Tree

1 байт убрано, 21:25, 10 июня 2014
add(v, c)
Чтобы прибавить константу на пути от <tex>v</tex> до корня link-cut-дерева вызовем <tex>expose(v)</tex>, что построит запрашиваемый путь в виде splay-дерева, в котором <tex>v</tex> - корень, и в левом поддереве находятся вершины, которые находятся выше чем <tex>v</tex> в link-cut-дереве (то есть все вершины пути без <tex>v</tex>), а в правом - те, что ниже. Тогда прибавим <tex>c</tex> к <tex>\Delta w(v)</tex> и вычтем константу от правого ребенка <tex>v</tex>, чтобы скомпенсировать разницу и сохранить инвариант.
'''function''' add(v : '''tree''', c : '''int''') :
expose(v)
<tex>\vartriangle</tex>w(v) += c
234
правки

Навигация