# Segment Tree Range Sum (Practice 4098): Scan
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 [try it free](https://www.linkjob.ai/).