234
правки
Изменения
→Решение задачи в частном случае
Чтобы прибавлять заданное число на пути от вершины до корня, будем в каждой вершине хранить величину <tex>\Delta w</tex>, которая равна разнице между весом вершины и весом её родителя. Для корня это значение равно весу самого корня. Поэтому вес вершины определятся следующим образом:
<tex>w(u) = \sum _displaystyle \sum_v^{v} \Delta w(v)</tex>, где сумма берется по всем предкам <tex>v — все предки вершины u</tex>, включая саму вершину.
При прибавлении <tex>\alpha</tex> на пути от вершины <tex>v</tex> до корня, сначала вызывается <tex>splay(v)</tex>, после чего в левом поддереве находятся вершины, которые лежат на пути к корню. Затем надо прибавить <tex>\alpha</tex> к <tex>\Delta w(v)</tex> и, чтобы сохранить веса вершин, которые находятся ниже в пути, вычесть <tex>\alpha</tex> от <tex>\Delta w(right(v))</tex>.
