# 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) ```python 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](https://www.linkjob.ai/), which offers real-time interview help.*