1. One-Liner
A segment tree stores aggregates (sum, min, …) over intervals of an array in a binary tree so range queries and point updates happen in O(log n).
2. The Problem It Solves
Static prefix sums help only some queries; you need range sum / min / gcd with updates. A segment tree splits [0, n−1] recursively into halves, each node covers one segment and caches its aggregate.
3. The Core Idea
Root = whole array. Children split the range mid. Leaves = single elements. Query walks O(log n) nodes whose segments partition the query range. Update changes one leaf and bubbles the combine up.
4. How It Works (Step-by-Step)
| Step | Action |
|---|---|
| 1 | Build recursively: node value = combine(children) or array[i] at leaf. |
| 2 | Range query [L,R]: if node range ⊆ [L,R], return node; if disjoint, return identity; else recurse to children. |
| 3 | Point update: set leaf, recompute ancestors. |
| 4 | Combine must be associative (sum, min, gcd—not always non-invertible ops without care). |
5. Dry Run Example
Array [1,2,3,4]. Sum query [1,2] (0-based): recurse from root; partial overlaps split until covered segments 2 and 3 sum to 5.
6. Key Properties
| Property | Detail |
|---|---|
| Height | O(log n) |
| Nodes | ≤ 4n in practice |
| Lazy | Range add with propagation |
7. Where It Is Used
| Area | Use |
|---|---|
| Competitive programming | Range queries |
| GIS / time series | Window aggregates |
| DB research | Augmented structures |
8. Interview Tips
Explain merge of partial answers. Discuss lazy propagation for range updates. Memory: 4×n array. Compare with Fenwick for sum-only simpler.
9. Comparison with Other Algorithms
| DS | Queries | Updates | Notes |
|---|---|---|---|
| Segment tree | O(log n) | O(log n) | General combine |
| Fenwick | O(log n) | O(log n) | Prefix/sum tricks |
| Sparse table | O(1) min | Static | No updates |
10. Complexity
| -- | -- |
|---|---|
| Build | O(n) |
| Query/Update | O(log n) |
| Space | O(n) |
Implementation Example (PYTHON)
def build(a, seg, idx, l, r):
if l == r:
seg[idx] = a[l]
return
m = (l + r) // 2
build(a, seg, 2*idx, l, m)
build(a, seg, 2*idx+1, m+1, r)
seg[idx] = seg[2*idx] + seg[2*idx+1]
def query(seg, idx, l, r, ql, qr):
if ql <= l and r <= qr:
return seg[idx]
if r < ql or l > qr:
return 0
m = (l + r) // 2
return query(seg,2*idx,l,m,ql,qr)+query(seg,2*idx+1,m+1,r,ql,qr)