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.
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
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 it
- 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.
Next recommended lesson
Continue through this topic with Least You Need to Know: Two Pointers, Sliding Windows, and String Scans.
Least You Need to Know: Two Pointers, Sliding Windows, and String ScansRelated lessons
Keep going with nearby lessons in the same topic.