Path Update

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: $O(\log n)$ amortized.