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: amortized.