The recursion
To query a slice, you recurse from the root, comparing the query range against each node's range. Three cases arise at every node.
- No overlap: the node range lies entirely outside the query, so return a neutral value such as zero for sums.
- Total cover: the node range sits fully inside the query, so return its stored aggregate without descending further.
- Partial overlap: recurse into both children and combine their answers.
Why only a few nodes matter
The recursion stops early whenever a node is fully inside the query. It turns out only a small number of nodes are ever needed to exactly tile any range, roughly two per level of the tree. That is why the query stays logarithmic rather than scanning the whole slice.
Choosing the neutral value
The neutral value depends on the operation you combine with. For sums it is zero, for minimums it is positive infinity, for maximums it is negative infinity. Returning the right neutral element for a no overlap node keeps the combine step correct.
A worked feel
Querying a middle slice will fully cover a couple of mid sized nodes on the left, fully cover a couple on the right, and trim the edges, then add those covered aggregates together.
Key idea
A range query descends the tree, returning stored aggregates for fully covered nodes and a neutral value for disjoint ones, combining the pieces.