Segment Tree
A powerful tree data structure for range queries (sum, min, max) and point/range updates in O(log n). Essential for competitive programming and advanced interview problems.
Segment Tree
A powerful tree data structure for range queries (sum, min, max) and point/range updates in O(log n). Essential for competitive programming and advanced interview problems.
Input: [1, 3, 5, 7, 9, 11]. Building Segment Tree for range sum queries.
Answer a range query
A segment tree over 8 elements answers sum(2..5). Sort each node by what the query does with it.
Tap a piece, then tap where it goes — or drag it. Tap the tray to take one back.
Fully inside — use its sum
Drop items herePartial — recurse into children
Drop items hereOutside — ignore
Drop items hereTest your knowledge
What is the key advantage of Segment Tree over Prefix Sum?
The short version
Imagine a company hierarchy. To find total sales for a region, the regional manager already has aggregated data from city managers, who have it from store managers. You don't sum every store - you query pre-computed subtotals at just the right level.
In more depth
The Power of Preprocessing
Segment Tree stores a tree of precomputed aggregate values (sum, min, max, etc.) for ranges of the array.
Structure:
Operations:
Lazy Propagation:
For range updates, defer updates to children until needed. Enables O(log n) range updates instead of O(n).
Key Gotchas:
When to reach for this
- Range queries + range/point updates
- Need O(log n) for both query and update
- Interval problems with modifications
- Count inversions, smaller elements after self
Interview Questions
Love this visualization?
Sign up to track your progress, earn achievements, use the AI assistant, and access your personal learning dashboard.
100% free • No credit card required