# Segment Tree Range Sum (Practice 4203): Walkthrough

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/).