Изменения

Для реализации <tex>\min</tex> будем хранить минимум уже для всего поддерева. Чтобы искать минимум от вершины <tex>v</tex>, надо вызвать <tex>splay(v)</tex> и сравнить её вес с минимумом левого поддерева, в котором теперь находятся все вершины пути кроме <tex>v</tex>. Определим <tex>\Delta \min(v)</tex> таким образом, чтобы сохранялся следующий инвариант: <tex>\min(v) = \Delta \min(v) + w(v) </tex>. Пусть <tex>l</tex> и <tex>r</tex> дети <tex>v</tex>, тогда

<tex>\min(v) = \min\{w(v), \ min(l), \ min(r)\}</tex>

<tex>\Delta \min(v) = \min(v) - w(v) \\= \min\{w(v) - w(v), \ min(l) - w(v), \ min(r) - w(v)\} \\= \min\{0, \ (\Delta \min(l) + w(l)) - w(v), \ (\Delta \min(r) + w(r)) - w(v)\} \\= \min\{0, \ \Delta \min(l) + \Delta w(l), \ \Delta \min(r) + \Delta w(r)\}</tex>