Update all nodes on path from u to v (add value, set value, etc.):
function pathUpdate(u, v, delta)
makeRoot(u)
access(v)
// Apply lazy update to v's auxiliary tree
v.lazy := v.lazy + delta
pushDownLazy(v)
Use lazy propagation for range updates:
function pushDownLazy(v)
if v.lazy != 0 then
v.value := v.value + v.lazy
if v.left then v.left.lazy := v.left.lazy + v.lazy
if v.right then v.right.lazy := v.right.lazy + v.lazy
v.lazy := 0
// Also handle reversal flag
pushDown(v)
Time: amortized.