Path Query

Query the aggregate (sum, min, max, etc.) on path from u to v:

function pathQuery(u, v)
    makeRoot(u)
    access(v)
    // Now path u-v is in v's auxiliary tree
    return v.subtreeAggregate

After makeRoot(u), u is the root. After access(v), the path from v to u (the root) is in one auxiliary tree.

Each node maintains aggregate of its subtree:

function updateAggregate(v)
    v.subtreeAggregate := combine(
        v.value,
        v.left.subtreeAggregate if v.left else identity,
        v.right.subtreeAggregate if v.right else identity
    )

Update aggregates bottom-up after rotations.

Time: $O(\log n)$ amortized.