Overview
A segment tree answers range queries (sum, min, max) and handles point or range updates in O(log n).
Analogy
A corporate org chart: each manager stores the summary (sum/max/min) of their entire team.
Step-by-step
- Build: O(n) — each node stores aggregate of its range.
- Query range [l,r]: recurse down, combine segments that fit inside [l,r].
- Point update: O(log n) — update leaf, recompute ancestors.
- Range update with lazy propagation: defer updates, apply when needed.
Visual
Node for [0,7] covers all 8 elements; node for [0,3] covers left half; leaf [2,2] covers arr[2].
Common mistakes
- Off-by-one in range boundaries (inclusive vs exclusive).
- Forgetting to propagate lazy tags before querying children.
Practice questions
- Build a sum segment tree; query sum of [l,r].
- Add lazy range-add update support.
Time
O(n) build, O(log n) query/update
AI Wisdom