Algorithms / Segment Tree Range Query
Least You Need to Know: Segment Trees, Range Queries, and Overlap Cases
Segment trees recursively partition an array into intervals so that range aggregates can be answered in `O(log n)` by combining a small number of stored interval results. The key interview idea is to reason about **no overlap**, **partial overlap**, and **complete overlap**.
The least you need to know
- A segment tree recursively splits an interval into left and right children.
- Range queries combine results from the nodes whose intervals cover the query.
- No-overlap cases return the identity element for the operation.
- Complete-overlap cases return a stored node value directly.
- The operation can be sum, min, max, gcd, and other associative aggregates.
Key notation
[l, r]
interval represented by a tree node
identity
neutral value for non-overlap, such as 0 for sum
combine
merge child answers into a parent answer
Tiny worked example
- The root covers the whole array.
- A sum query on a subrange recursively visits only nodes whose intervals overlap that subrange.
- Fully covered nodes contribute their stored sums directly.
- Non-overlapping nodes contribute zero, the identity for addition.
Common mistakes
- Students sometimes recurse into both children even when there is complete overlap and a stored value is enough.
- The identity element depends on the operation: 0 for sum, infinity for min, and so on.
- Segment trees support many associative aggregates, not only sums.
How to recognize this kind of problem
- The prompt needs many range queries and updates over an array.
- A static prefix sum is not enough because updates or more complex aggregates are needed.
- You can reason about interval overlap cases recursively.