What is a Segment Tree?
Learn what a segment tree is, how range queries and lazy propagation work, and how to answer this interview question well.
Expected Interview Answer
A segment tree is a binary tree built over an array that stores a precomputed aggregate (sum, min, max, or similar) for every contiguous sub-range at each node, letting range queries and point or range updates both run in O(log n) time instead of O(n).
The tree is typically stored implicitly in an array where each internal node represents the aggregate of a range, its left child covers the first half of that range and its right child covers the second half, recursively down to leaves that represent single elements. Building the tree takes O(n) time since there are 2n-1 nodes total. A range query decomposes the requested range into at most O(log n) pre-aggregated node ranges that exactly cover it, combining their stored values without touching individual elements. A point update walks from the corresponding leaf up to the root, recomputing O(log n) ancestor aggregates along the way; range updates use an additional technique called lazy propagation to defer pushing updates down until a query actually needs that subtree, keeping range updates O(log n) as well instead of O(n). Segment trees are the standard tool for range-sum, range-minimum, or range-maximum queries with frequent updates, beating a plain prefix-sum array whenever updates are common.
- O(log n) range query and O(log n) update, both directions
- Handles range-sum, range-min, range-max, and custom aggregates
- O(n) build time with 2n-1 total nodes
- Lazy propagation extends it to O(log n) range updates
AI Mentor Explanation
A segment tree is like a scoring ledger that keeps a running total not just per over but for every larger grouping of overs, all the way up to the full innings. Instead of adding up every single ball to answer "what was the total in overs 12 through 27", the ledger already has precomputed totals for chunks like overs 12-19 and 20-27 sitting ready, so it just combines a handful of chunk totals. When one ball's result is corrected after review, only the chunks containing that ball need their totals refreshed, walking up from the smallest chunk to the full innings total, not the whole ledger. This precomputed, hierarchical chunking is what turns a slow ball-by-ball recount into a quick handful of lookups.
Step-by-Step Explanation
Step 1
Build recursively
Each node covers a range; leaves hold single elements; internal nodes store the aggregate of their two children’s ranges, built in O(n).
Step 2
Query by decomposition
Split the requested range into at most O(log n) node ranges that exactly cover it, then combine their stored aggregates.
Step 3
Point update
Update the corresponding leaf, then walk up recomputing each ancestor’s aggregate, O(log n) total.
Step 4
Range update with lazy propagation
Defer pushing an update into child nodes until a query actually needs that subtree, keeping range updates O(log n).
What Interviewer Expects
- Explain how range queries decompose into O(log n) pre-aggregated nodes
- State both O(log n) query and O(log n) update time complexities
- Describe lazy propagation and why it is needed for efficient range updates
- Compare against a plain prefix-sum array and when each is preferable
Common Mistakes
- Confusing a segment tree with a Fenwick tree (binary indexed tree), which is more limited but simpler
- Forgetting lazy propagation, causing range updates to degrade to O(n)
- Not recomputing ancestor aggregates all the way to the root after a point update
- Assuming a prefix-sum array is always sufficient, ignoring frequent-update workloads
Best Answer (HR Friendly)
“A segment tree precomputes answers for chunks of a range so I can answer any "what's the total (or min/max) between these two positions" question by combining a handful of precomputed chunks instead of scanning everything. It also lets me update a value and only refresh the small number of chunks that contain it, so both queries and updates stay fast even on huge datasets.”
Code Example
class SegmentTree:
def __init__(self, data):
self.n = len(data)
self.tree = [0] * (2 * self.n)
for i in range(self.n):
self.tree[self.n + i] = data[i]
for i in range(self.n - 1, 0, -1):
self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]
def update(self, pos, value):
i = pos + self.n
self.tree[i] = value
while i > 1:
i //= 2
self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]
def query(self, left, right):
# sum over [left, right)
result = 0
left += self.n
right += self.n
while left < right:
if left % 2 == 1:
result += self.tree[left]
left += 1
if right % 2 == 1:
right -= 1
result += self.tree[right]
left //= 2
right //= 2
return result
seg = SegmentTree([1, 3, 5, 7, 9, 11])
print(seg.query(1, 4)) # sum of indices 1..3 => 15
seg.update(1, 10)
print(seg.query(1, 4)) # updated sum => 22Follow-up Questions
- How does a segment tree compare to a Fenwick tree (binary indexed tree)?
- How does lazy propagation keep range updates at O(log n)?
- How would you adapt a segment tree for range-minimum queries instead of range-sum?
- How would you build a persistent segment tree to query past versions of the array?
MCQ Practice
1. What is the time complexity of a range query on a segment tree?
A range query decomposes into at most O(log n) pre-aggregated node ranges that are combined.
2. What technique allows range updates to also run in O(log n) instead of O(n)?
Lazy propagation defers pushing an update into child subtrees until a query actually needs them.
3. How many total nodes does a segment tree over n elements typically have?
A segment tree has n leaves and n-1 internal nodes, for about 2n - 1 total nodes.
Flash Cards
What does a segment tree let you compute in O(log n)? — Range aggregate queries (sum, min, max) and point or range updates.
How does a range query work internally? — It decomposes the range into at most O(log n) pre-aggregated node ranges and combines them.
What technique enables efficient range updates? — Lazy propagation, which defers pushing updates into child subtrees until needed.
What is the build time complexity of a segment tree? — O(n), since there are about 2n - 1 nodes total.