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