Segment Tree
Software Engineer path · lesson 19 of 99A 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.
Syntax: query n n · update n n. Numbers from -50 to 50.
2–8 whole numbers between −50 and 50.
Build a sum tree over 6 values; each node stores the sum of a range.
- 1build(node, lo, hi): leaf → arr[lo]; else build both halves, tree[node] = left + right
- 2query(node, lo, hi, l, r):
- 3 if [lo, hi] is outside [l, r]: return 0
- 4 if [lo, hi] is inside [l, r]: return tree[node] # use it whole
- 5 return query(left half) + query(right half) # partial overlap
- 6update(i, v): set the leaf, then recompute every ancestor
- Nodes visited
- 0 / 21
Tap any element in the diagram to inspect its state at this step.
Keys: ← → step, Space play/pause. Predict mode pauses before key steps and asks what happens next.
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
References & Further Reading
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