Overview
A Segment Tree is a binary tree of interval aggregates that answers range queries — such as the sum over a sub-array — and applies point updates, both in logarithmic time. Each node stores the aggregate of a contiguous segment of the array.
The root covers the whole array; each node splits its range into two halves handled by its children, down to single-element leaves. This lets a query cover any range by combining O(log n) precomputed segments.
How Segment Tree works
- Build recursively: each internal node's value is the sum of its two children's values.
- A range-sum query descends from the root, taking whole nodes that lie inside the range and splitting those that straddle it.
- A point update changes one leaf, then walks back up recomputing each ancestor's aggregate.
- Because each query or update touches at most two nodes per level, the work is O(log n).
When to use it
- Range-sum, range-minimum, or range-maximum queries over a mutable array.
- Competitive programming problems mixing many updates with many range queries.
- Interval bookkeeping such as cumulative statistics, histograms, and range frequency counts.
Complexity analysis
Building the tree is O(n), while each range query and each point update is O(log n). The structure uses O(n) space (commonly a flat array of about 2n–4n nodes). Range updates can be made O(log n) too with lazy propagation.
Frequently asked questions
When should I use a segment tree instead of a prefix-sum array?
A prefix-sum array answers range sums in O(1) but needs O(n) to rebuild after an update. A segment tree keeps both queries and updates at O(log n), so it wins whenever the data changes often.
What is lazy propagation?
It defers updates that apply to a whole range by storing a pending value at a node and pushing it down only when needed, letting range updates run in O(log n) instead of O(n).