Segment Trees for Interviews: Range Queries with Updates
Prefix sums answer range-sum queries in O(1), but a single update costs O(n). When a problem mixes point updates and range queries (LeetCode 307, Range Sum Query - Mutable), a segment tree gives O(log n) for both.
Iterative segment tree (compact version)
class SegTree:
def __init__(self, nums):
self.n = len(nums)
self.t = [0] * (2 * self.n)
self.t[self.n:] = nums
for i in range(self.n - 1, 0, -1):
self.t[i] = self.t[2 * i] + self.t[2 * i + 1]
def update(self, i, val):
i += self.n
self.t[i] = val
while i > 1:
i //= 2
self.t[i] = self.t[2 * i] + self.t[2 * i + 1]
def query(self, l, r): # inclusive l..r
res, l, r = 0, l + self.n, r + self.n + 1
while l < r:
if l & 1: res += self.t[l]; l += 1
if r & 1: r -= 1; res += self.t[r]
l //= 2; r //= 2
return res
Swap + for min, max or gcd to support other associative operations.
When an interviewer expects it
- Range updates and range queries: mention lazy propagation.
- Counting inversions or "count of smaller numbers after self" (315): a segment tree or Fenwick tree over value ranks.
Fenwick tree comparison
A Fenwick (binary indexed) tree is shorter to write and enough for prefix sums, but a segment tree handles min/max and lazy range updates more naturally. Saying which you'd pick and why is often worth more than the code.
Disclosure: I work on Linkjob.ai, which offers real-time interview help.