6 views
# Segment Tree Range Sum (Practice 4728): Pattern Interviewers love segment tree range sum because it checks whether you can state the invariant before coding. Here is a compact rehearsal note. ## Approach Build tree over leaves; query by covering nodes. ```python class SegTree: def __init__(self, a): n = len(a); self.n = n; self.t = [0]*(4*n) def build(i, l, r): if l == r: self.t[i] = a[l]; return m = (l+r)//2; build(2*i, l, m); build(2*i+1, m+1, r) self.t[i] = self.t[2*i] + self.t[2*i+1] if n: build(1, 0, n-1) def query(self, ql, qr): def rec(i, l, r): if qr < l or r < ql: return 0 if ql <= l and r <= qr: return self.t[i] m = (l+r)//2 return rec(2*i, l, m) + rec(2*i+1, m+1, r) return rec(1, 0, self.n-1) ``` ## Complexity Linear in the dominant input size for the scan; heap/tree variants add a log factor. ## Interview pitfalls State the invariant out loud, name the complexity, then code. Skipping the invariant is the usual fail mode. ## Practicing out loud Narrate the approach, complexity and one edge case in under a minute. Disclosure: I work on Linkjob AI, a real-time interview assistant. If you want live practice help, see [the Linkjob AI app](https://www.linkjob.ai/).