Segment Tree Interview Patterns (2025)
Segment Trees are powerful data structures for range query problems — they answer range sum, range min/max, and range update queries in O(log n) time. They appear in competitive programming and senior-level FAANG interviews where brute-force O(n) per query is too slow.
When to Use a Segment Tree
- Range queries (sum, min, max, GCD) with point or range updates
- Point updates with range queries: “update index i, then query sum of [l, r]”
- Range updates with range queries: “add v to all elements in [l, r], then query min of [l’, r’]” (requires lazy propagation)
- Brute force is O(n) per query; Segment Tree is O(log n) per operation
Core Implementation: Range Sum with Point Updates
class SegmentTree:
"""
Segment Tree for range sum queries with point updates.
0-indexed. Internal array is 1-indexed (root at index 1).
"""
def __init__(self, nums: list[int]):
self.n = len(nums)
self.tree = [0] * (4 * self.n) # 4n space is always sufficient
if nums:
self._build(nums, 1, 0, self.n - 1)
def _build(self, nums: list[int], node: int, start: int, end: int):
if start == end:
self.tree[node] = nums[start]
else:
mid = (start + end) // 2
self._build(nums, 2 * node, start, mid)
self._build(nums, 2 * node + 1, mid + 1, end)
self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]
def update(self, idx: int, val: int):
"""Update index idx to value val. O(log n)."""
self._update(1, 0, self.n - 1, idx, val)
def _update(self, node: int, start: int, end: int, idx: int, val: int):
if start == end:
self.tree[node] = val
else:
mid = (start + end) // 2
if idx int:
"""Sum of elements in [l, r] inclusive. O(log n)."""
return self._query(1, 0, self.n - 1, l, r)
def _query(self, node: int, start: int, end: int, l: int, r: int) -> int:
if r < start or end < l: # No overlap
return 0
if l <= start and end <= r: # Total overlap
return self.tree[node]
mid = (start + end) // 2 # Partial overlap: recurse both children
return (self._query(2 * node, start, mid, l, r) +
self._query(2 * node + 1, mid + 1, end, l, r))Range Min / Max Segment Tree
class RangeMinTree:
"""Replace sum with min; neutral element is float('inf')."""
def __init__(self, nums: list[int]):
self.n = len(nums)
self.tree = [float('inf')] * (4 * self.n)
self._build(nums, 1, 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, start, mid)
self._build(nums, 2*node+1, mid+1, end)
self.tree[node] = min(self.tree[2*node], self.tree[2*node+1])
def query_min(self, l: int, r: int) -> int:
return self._query(1, 0, self.n-1, l, r)
def _query(self, node, start, end, l, r):
if r < start or end < l: return float('inf')
if l <= start and end <= r: return self.tree[node]
mid = (start + end) // 2
return min(self._query(2*node, start, mid, l, r),
self._query(2*node+1, mid+1, end, l, r))
def update(self, idx: int, val: int):
self._update(1, 0, self.n-1, idx, val)
def _update(self, node, start, end, idx, val):
if start == end:
self.tree[node] = val
else:
mid = (start + end) // 2
if idx <= mid: self._update(2*node, start, mid, idx, val)
else: self._update(2*node+1, mid+1, end, idx, val)
self.tree[node] = min(self.tree[2*node], self.tree[2*node+1])Lazy Propagation (Range Updates)
Without lazy propagation, a range update “add 5 to all elements in [l, r]” takes O(n) time. Lazy propagation defers the update to child nodes until they are actually queried, keeping updates to O(log n).
class LazySegmentTree:
"""
Segment Tree with lazy propagation.
Supports: range add update + range sum query. Both O(log n).
"""
def __init__(self, nums: list[int]):
self.n = len(nums)
self.tree = [0] * (4 * self.n)
self.lazy = [0] * (4 * self.n) # Pending additions
self._build(nums, 1, 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, start, mid)
self._build(nums, 2*node+1, mid+1, end)
self.tree[node] = self.tree[2*node] + self.tree[2*node+1]
def _push_down(self, node: int, start: int, end: int):
"""Propagate lazy value to children before going deeper."""
if self.lazy[node] != 0:
mid = (start + end) // 2
left_len = mid - start + 1
right_len = end - mid
self.tree[2*node] += self.lazy[node] * left_len
self.lazy[2*node] += self.lazy[node]
self.tree[2*node+1] += self.lazy[node] * right_len
self.lazy[2*node+1] += self.lazy[node]
self.lazy[node] = 0 # Consumed
def range_add(self, l: int, r: int, val: int):
"""Add val to all elements in [l, r]. O(log n)."""
self._range_add(1, 0, self.n-1, l, r, val)
def _range_add(self, node, start, end, l, r, val):
if r < start or end < l:
return
if l <= start and end int:
"""Sum of [l, r]. O(log n)."""
return self._range_sum(1, 0, self.n-1, l, r)
def _range_sum(self, node, start, end, l, r):
if r < start or end < l: return 0
if l <= start and end <= r: return self.tree[node]
self._push_down(node, start, end)
mid = (start + end) // 2
return (self._range_sum(2*node, start, mid, l, r) +
self._range_sum(2*node+1, mid+1, end, l, r))Classic Interview Problems Using Segment Trees
307. Range Sum Query — Mutable
class NumArray:
def __init__(self, nums: list[int]):
self.st = SegmentTree(nums)
def update(self, index: int, val: int):
self.st.update(index, val)
def sumRange(self, left: int, right: int) -> int:
return self.st.query(left, right)Count of Smaller Numbers After Self
def countSmaller(nums: list[int]) -> list[int]:
"""
For each element, count how many elements to its right are smaller.
Use coordinate compression + segment tree for O(n log n).
"""
# Coordinate compress to range [1, n]
sorted_unique = sorted(set(nums))
rank = {v: i+1 for i, v in enumerate(sorted_unique)}
n = len(sorted_unique)
tree = [0] * (4 * (n + 1))
def update(node, start, end, idx):
if start == end:
tree[node] += 1
return
mid = (start + end) // 2
if idx <= mid: update(2*node, start, mid, idx)
else: update(2*node+1, mid+1, end, idx)
tree[node] = tree[2*node] + tree[2*node+1]
def query(node, start, end, l, r):
if r < start or end < l: return 0
if l <= start and end <= r: return tree[node]
mid = (start + end) // 2
return (query(2*node, start, mid, l, r) +
query(2*node+1, mid+1, end, l, r))
result = []
for num in reversed(nums):
r = rank[num]
count = query(1, 1, n, 1, r - 1) # Count elements smaller than num
result.append(count)
update(1, 1, n, r)
return result[::-1]Fenwick Tree (Binary Indexed Tree) — Simpler Alternative
class FenwickTree:
"""
Simpler than Segment Tree; supports point update + prefix sum.
Cannot do range updates or range min/max (for those, use Segment Tree).
1-indexed internally.
"""
def __init__(self, n: int):
self.n = n
self.tree = [0] * (n + 1)
def update(self, i: int, delta: int):
"""Add delta to position i (1-indexed). O(log n)."""
while i int:
"""Sum of [1..i]. O(log n)."""
s = 0
while i > 0:
s += self.tree[i]
i -= i & (-i) # Remove lowest set bit
return s
def range_sum(self, l: int, r: int) -> int:
"""Sum of [l..r] (1-indexed). O(log n)."""
return self.prefix_sum(r) - self.prefix_sum(l - 1)
# Usage: Range Sum Query — Mutable using BIT
class NumArrayBIT:
def __init__(self, nums: list[int]):
self.n = len(nums)
self.bit = FenwickTree(self.n)
self.nums = nums[:]
for i, v in enumerate(nums):
self.bit.update(i + 1, v) # 1-indexed
def update(self, index: int, val: int):
self.bit.update(index + 1, val - self.nums[index])
self.nums[index] = val
def sumRange(self, left: int, right: int) -> int:
return self.bit.range_sum(left + 1, right + 1)Segment Tree vs Fenwick Tree
| Feature | Segment Tree | Fenwick Tree (BIT) |
|---|---|---|
| Point update + range sum | Yes O(log n) | Yes O(log n) |
| Range update + range query | Yes (lazy) O(log n) | Limited (range add + range sum only) |
| Range min/max | Yes O(log n) | No |
| Implementation complexity | High | Low (5-10 lines) |
| Space | O(4n) | O(n) |
| Constant factor | Larger | Smaller |
Complexity Summary
- Build: O(n)
- Point update: O(log n)
- Range query: O(log n)
- Range update with lazy propagation: O(log n)
- Space: O(4n) — always allocate 4×n to be safe
{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”What is a Segment Tree and when should you use it?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”A Segment Tree is a binary tree where each node stores an aggregate (sum, min, max) for a range of array elements. Use it when you need both updates and range queries — brute force is O(n) per query, a Segment Tree gives O(log n) for both. Use cases: range sum with point updates (LeetCode 307), range min/max queries, count of inversions, count of smaller elements. If you only need prefix sums with no updates, a prefix sum array suffices.”}},{“@type”:”Question”,”name”:”What is lazy propagation in a Segment Tree?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Lazy propagation defers updates to child nodes until they are actually needed. Without it, adding a value to all elements in range [l, r] requires O(n) leaf updates. With lazy propagation, you mark a node with a “pending” value and only push it to children when you need to recurse deeper. This keeps both range updates and range queries at O(log n). The push_down function propagates the lazy value to both children before recursing into them.”}},{“@type”:”Question”,”name”:”What is the difference between a Segment Tree and a Fenwick Tree?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Fenwick Tree (Binary Indexed Tree) supports point update and prefix sum in O(log n) with very simple code (5-10 lines). Segment Tree supports everything BIT does, plus range min/max queries and range updates with lazy propagation. Use a Fenwick Tree when you only need sum queries — it’s faster in practice (smaller constant) and easier to implement. Use a Segment Tree when you need range min/max, arbitrary aggregations, or range updates.”}},{“@type”:”Question”,”name”:”How much space does a Segment Tree need?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Allocate 4×n elements for the tree array, where n is the input array size. This is always sufficient regardless of n. The tree is stored as a 1-indexed array where node i has children at 2i (left) and 2i+1 (right), with the root at index 1. Building the tree takes O(n) time by recursively computing aggregates bottom-up. The 4n bound accounts for the tree potentially being padded to the next power of 2.”}}]}
🏢 Asked at: Databricks Interview Guide 2026: Spark Internals, Delta Lake, and Lakehouse Architecture
🏢 Asked at: Meta Interview Guide 2026: Facebook, Instagram, WhatsApp Engineering
🏢 Asked at: Uber Interview Guide 2026: Dispatch Systems, Geospatial Algorithms, and Marketplace Engineering
🏢 Asked at: Coinbase Interview Guide
🏢 Asked at: Atlassian Interview Guide
🏢 Asked at: Apple Interview Guide 2026: iOS Systems, Hardware-Software Integration, and iCloud Architecture