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**.
جو کم از کم جاننا ضروری ہے
- 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.
اہم علامتیں
[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
مختصر حل شدہ مثال
- 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.
عام غلطیاں
- 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.
اس قسم کے سوال کو کیسے پہچانیں
- 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.