Segment Tree
A binary tree over an array where each node stores an aggregate (sum, min, max…) of a range. Both point updates and range queries cost O(log n), by combining at most O(log n) precomputed sub-ranges instead of scanning.
A segment tree splits an array into a binary tree of ranges: the root covers the whole array, each internal node covers half of its parent's range, and leaves cover single elements. Every node stores an aggregate of its range, computed bottom-up from its children.
A range query [l, r] recurses from the root: a node fully inside [l, r] contributes its precomputed aggregate immediately (no need to look inside it); a node fully outside contributes nothing; a node straddling the boundary recurses into both children. Only O(log n) nodes are ever visited, because at each depth at most a constant number of nodes straddle the boundary.
A point update walks the single root-to-leaf path for the changed index, updating the aggregate at every ancestor on the way — O(log n) nodes touched, O(log n) time. Lazy propagation extends the same idea to O(log n) range updates by deferring pushes to children until they are actually queried.
Operations
| Operation | Complexity |
|---|---|
| build | O(n) |
| point update | O(log n) |
| range query | O(log n) |
| space | O(n) |
Where it's used
Range-sum/min/max queries with updates: competitive programming, interval scheduling, computational geometry sweep lines, database range indexes.