Segment Tree and Range Query Interview Patterns
Segment trees solve range query problems — finding the sum, min, max, or GCD over an array interval — with O(log n) query and update time. They appear in hard LeetCode problems and senior-level interviews at companies that care about algorithmic depth. This guide covers the implementation and the pattern recognition needed to apply them correctly.
When to Use a Segment Tree
Use a segment tree when you need both:
- Range queries: sum/min/max/GCD over array[i..j]
- Point updates: update a single element
Complexity: O(n) build, O(log n) query and update. Prefix sum arrays are O(1) query but O(n) update. Segment trees are the right tool when you need both operations to be fast.
Implementation: Sum Segment Tree
class SegmentTree:
def __init__(self, nums):
self.n = len(nums)
self.tree = [0] * (4 * self.n)
self._build(nums, 0, 0, self.n - 1)
def _build(self, nums, node, start, end):
if start == end:
self.tree[node] = nums[start]
else:
mid = (start + end) // 2
self._build(nums, 2*node+1, start, mid)
self._build(nums, 2*node+2, mid+1, end)
self.tree[node] = self.tree[2*node+1] + self.tree[2*node+2]
def update(self, idx, val, node=0, start=0, end=None):
if end is None: end = self.n - 1
if start == end:
self.tree[node] = val
return
mid = (start + end) // 2
if idx <= mid: self.update(idx, val, 2*node+1, start, mid)
else: self.update(idx, val, 2*node+2, mid+1, end)
self.tree[node] = self.tree[2*node+1] + self.tree[2*node+2]
def query(self, l, r, node=0, start=0, end=None):
if end is None: end = self.n - 1
if r < start or end < l: return 0 # out of range
if l <= start and end <= r: return self.tree[node] # fully covered
mid = (start + end) // 2
return (self.query(l, r, 2*node+1, start, mid) +
self.query(l, r, 2*node+2, mid+1, end))Range Sum Query – Mutable (LeetCode 307)
class NumArray:
def __init__(self, nums):
self.st = SegmentTree(nums)
def update(self, index, val):
self.st.update(index, val)
def sumRange(self, left, right):
return self.st.query(left, right)Binary Indexed Tree (Fenwick Tree) — Simpler for Range Sum
When you only need range sum + point update (not min/max/other operations), the Fenwick tree is simpler to implement:
class BIT:
def __init__(self, n):
self.n = n
self.tree = [0] * (n + 1)
def update(self, i, delta): # i is 1-indexed
while i 0:
s += self.tree[i]
i -= i & (-i) # remove lowest set bit
return s
def range_sum(self, l, r):
return self.prefix_sum(r) - self.prefix_sum(l - 1)Fenwick tree uses O(n) space (vs. O(4n) for segment tree), has simpler code, but only supports commutative/invertible operations (sum, XOR). Use segment tree for min/max.
Count of Smaller Numbers After Self (LeetCode 315)
For each element, count how many elements to its right are smaller. Use a Fenwick tree over value coordinates:
def count_smaller(nums):
# Coordinate compress: map values to [1..n]
sorted_unique = sorted(set(nums))
rank = {v: i+1 for i, v in enumerate(sorted_unique)}
n = len(nums)
bit = BIT(len(sorted_unique))
result = []
for num in reversed(nums):
r = rank[num]
result.append(bit.prefix_sum(r - 1)) # count elements with rank < r
bit.update(r, 1) # register this element
return result[::-1]Lazy Propagation (Range Update)
When you need range updates (add 5 to all elements in [l..r]) and range queries, use lazy propagation to defer updates:
# Standard segment tree pushes updates down to children only when queried.
# lazy[node] stores a pending update not yet applied to children.
# On query/update reaching a node with lazy != 0:
# 1. Apply lazy to node value
# 2. Push lazy to children: lazy[2*node+1] += lazy[node]; lazy[2*node+2] += lazy[node]
# 3. Clear: lazy[node] = 0
# This keeps range update at O(log n) instead of O(n).Common Problems by Pattern
| Problem Type | Tool | LeetCode |
|---|---|---|
| Range sum, point update | Fenwick tree | 307, 315, 327 |
| Range min/max, point update | Segment tree | 699, 715, 2407 |
| Range update, range query | Segment tree + lazy | 732, 1505 |
| Order statistics (kth smallest) | Segment tree on values | 315, 493, 2426 |
Interview Tips
- Implement Fenwick tree for range sum — it is 15 lines vs. 40+ for segment tree and impresses interviewers with conciseness
- The lowbit trick
i & (-i)is the key to the Fenwick tree — explain it: -i in two's complement flips all bits and adds 1, leaving only the lowest set bit - When asked about range min/max, pivot to segment tree and explain why Fenwick doesn't work (min is not invertible)
- For the coordinate compression pattern (used in 315, 327, 493) — sorting values and mapping to ranks is a powerful technique beyond segment trees
{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “When should you use a segment tree vs. a Fenwick tree vs. a prefix sum array?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “Prefix sum array: O(n) build, O(1) range query, O(n) point update. Use when the array is immutable. Fenwick tree (Binary Indexed Tree): O(n) build, O(log n) range sum query, O(log n) point update. Use for range sum with updates – simpler code than segment tree. Only works for invertible operations (sum, XOR). Segment tree: O(n) build, O(log n) any range query (sum, min, max, GCD), O(log n) point update, O(log n) range update with lazy propagation. Use when: (1) you need range min/max (Fenwick tree cannot do this), (2) you need range updates, (3) you need custom aggregation functions. The rule: reach for Fenwick first for range sum; use segment tree when Fenwick is insufficient.” }
},
{
“@type”: “Question”,
“name”: “How does the Fenwick tree (BIT) lowbit trick work?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “The lowbit of i is i & (-i), which extracts the least significant set bit. In two's complement, -i = ~i + 1, which flips all bits then adds 1, leaving only the lowest set bit unchanged. In the Fenwick tree, each index i stores the sum of elements in a range whose length is determined by lowbit(i): tree[i] covers [i – lowbit(i) + 1, i]. For update(i): add delta to tree[i] and propagate up by repeatedly doing i += lowbit(i). For prefix_sum(i): sum tree[i] and go down by doing i -= lowbit(i). Each update touches O(log n) nodes (one per bit in i). This gives O(log n) update and query with just array indexing – no tree structure needed.” }
},
{
“@type”: “Question”,
“name”: “How do you solve Count of Smaller Numbers After Self using a Fenwick tree?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “The key insight: process elements right to left. For each element, query how many smaller elements have already been seen (i.e., are to the right). Use a Fenwick tree indexed by element value (coordinate-compressed to [1..n]). Algorithm: (1) sort unique values and assign ranks 1..k, (2) traverse nums right to left, (3) for each num with rank r: query prefix_sum(r-1) for count of smaller elements seen so far, then update(r, 1) to register this element, (4) prepend the count to result. Coordinate compression maps arbitrary values to [1..n] for use as Fenwick tree indices. Time: O(n log n). This pattern (offline + Fenwick + coordinate compression) solves LeetCode 315, 327, 493.” }
}
]
}