Range Query Operations
What you'll learn: How to efficiently answer aggregate queries (like sum, min, or max) over any range of an array using a segment tree in logarithmic time.
The Core Problem
Imagine you have an array of numbers and need to frequently answer questions like "What's the sum of elements from index 5 to 12?" or "What's the minimum value between indices 3 and 8?"
A naive approach would scan every element in the range each time—taking O(n) time per query. With a segment tree you've already built, you can answer these queries in O(log n) time by cleverly combining precomputed information.
How Range Queries Work
The segment tree stores aggregate values (sum, min, max, etc.) for every possible segment. When you query a range [L, R]:
- Start at the root and recursively descend
- If a node's range is completely inside [L, R], use its stored value directly—no need to go deeper
- If a node's range partially overlaps [L, R], split into left and right children and continue
- If no overlap, ignore that subtree entirely
- Combine the results from relevant nodes using your operation (addition for sum, comparison for min/max)
The Magic: Logarithmic Depth
Because the tree height is O(log n), and at each level you visit at most a constant number of nodes on the "boundary" of your query range, the total work is O(log n).
Analogy: Instead of counting every person in rows 5-12 of a stadium, you ask section managers who already know their totals, combining only the relevant sections' reports.
Key Takeaway: Range queries on segment trees combine precomputed segment values in O(log n) time by intelligently selecting nodes whose ranges fit completely within the query, avoiding unnecessary traversal of irrelevant subtrees.