Segment tree
hardEvery node owns a range; any query decomposes into at most 2 log n precomputed pieces. Three cases - no overlap, total overlap, partial - and only the third recurses.
O(log n) query and updateSpace O(4n)Saved in this browser - no sign-up, nothing sent anywhere.
How segment tree works
Every node owns a slice of the array and stores one combined value for it: a leaf owns a single index, a parent owns the union of its two children, the root owns everything. Build runs bottom-up in O(n) - leaves copy the raw values, each parent combines its children. The result is the array's aggregates precomputed at every scale, ready to be assembled into any range.
A query classifies each node it meets. No overlap with the query range: return the identity and stop. Total overlap: the node's stored value is exactly right - return it and stop. Partial overlap: recurse into both children. Only the third case descends, and at most two nodes per level are partial, which is why any query touches O(log n) nodes and assembles at most 2 log n pieces.
The structure earns its keep when data changes. A prefix-sum array answers range sums in O(1), but a single update invalidates the entire tail - O(n) to rebuild. A segment tree answers and updates both in O(log n): rewrite one leaf, recompute the path to the root. And any associative operation fits the same skeleton - sum, min, max, gcd - only the combine function changes.
Step by step
- Build a sum tree over [5, 8, 6, 3, 2, 7, 2, 6]. Leaves hold the raw values, each parent the sum of its children, the root 39.
- Query the sum of a[2..6]. The root's range [0..7] partially overlaps the query, so it splits into [0..3] and [4..7].
- [0..3] is partial too. Its child [0..1] is disjoint from the query - return 0 and prune that branch entirely.
- Its other child [2..3] lies fully inside the query. Return its stored 9 without ever touching its children.
- On the right, [4..5] is fully covered and contributes its stored 9; [6..7] splits - leaf [6] gives 2, leaf [7] is disjoint.
- Combine 9 + 9 + 2 = 20 from three precomputed nodes, having visited nine of the fifteen. A scan would read five cells but breaks under updates.
- Update a[4]: rewrite that leaf, then recompute [4..5], [4..7], and the root - four nodes, and every later query sees the change.
Complexity
| Worst case time | O(log n) query and update |
|---|---|
| Space | O(4n) |
Any range splits into O(log n) canonical nodes.
Reference implementation
Python
class SegmentTree:
def __init__(self, a):
self.n = len(a)
self.t = [0] * (4 * self.n)
self._build(1, 0, self.n - 1, a)
def _build(self, node, lo, hi, a):
if lo == hi:
self.t[node] = a[lo]
return
mid = (lo + hi) // 2
self._build(2 * node, lo, mid, a)
self._build(2 * node + 1, mid + 1, hi, a)
self.t[node] = self.t[2 * node] + self.t[2 * node + 1]
def query(self, l, r, node=1, lo=0, hi=None):
hi = self.n - 1 if hi is None else hi
if r < lo or hi < l: # disjoint
return 0
if l <= lo and hi <= r: # fully inside
return self.t[node]
mid = (lo + hi) // 2
return (self.query(l, r, 2 * node, lo, mid) +
self.query(l, r, 2 * node + 1, mid + 1, hi))
def update(self, i, v, node=1, lo=0, hi=None):
hi = self.n - 1 if hi is None else hi
if lo == hi:
self.t[node] = v
return
mid = (lo + hi) // 2
if i <= mid: self.update(i, v, 2 * node, lo, mid)
else: self.update(i, v, 2 * node + 1, mid + 1, hi)
self.t[node] = self.t[2 * node] + self.t[2 * node + 1]JavaScript
class SegmentTree {
constructor(a) {
this.n = a.length;
this.t = new Array(4 * this.n).fill(0);
this.#build(1, 0, this.n - 1, a);
}
#build(node, lo, hi, a) {
if (lo === hi) { this.t[node] = a[lo]; return; }
const mid = (lo + hi) >> 1;
this.#build(2 * node, lo, mid, a);
this.#build(2 * node + 1, mid + 1, hi, a);
this.t[node] = this.t[2 * node] + this.t[2 * node + 1];
}
query(l, r, node = 1, lo = 0, hi = this.n - 1) {
if (r < lo || hi < l) return 0; // disjoint
if (l <= lo && hi <= r) return this.t[node]; // covered
const mid = (lo + hi) >> 1;
return this.query(l, r, 2 * node, lo, mid) +
this.query(l, r, 2 * node + 1, mid + 1, hi);
}
}Worth noticing
Every node owns a range; the root owns everything
A leaf covers one index, a parent covers the union of its children. Any query range decomposes into at most 2·log n of these precomputed pieces - which is where the O(log n) comes from.
Three cases, and only one recurses
No overlap: return the identity and stop. Total overlap: return the stored value and stop. Partial overlap: split. The first two are what prune the recursion down to logarithmic size.
It beats a prefix sum when values change
Prefix sums answer range queries in O(1), but a single update invalidates the whole tail - O(n) to repair. A segment tree does both query and update in O(log n), which is the right trade whenever the data is live.
Any associative operation works
Switch between sum, min and max above: only the combine function changes. GCD, bitwise OR, matrix product, 'maximum subarray sum in range' - all fit the same skeleton, because associativity is the only thing the merge step needs.
Common pitfalls
- Allocating 2n cells for the tree. Unless n is a power of two the recursive layout overflows; 4n is the safe bound - this build pads n up to the next power of two instead.
- Wrong identity element. Sum's identity is 0, but min needs +Infinity and max needs -Infinity - returning 0 from a disjoint node in a min query corrupts the answer invisibly.
- Forgetting to recompute ancestors after a point update. Change the leaf alone and every query crossing it keeps returning stale aggregates.
- Using a non-associative combine. Averages of averages are wrong - store a sum and a count as a pair and divide only at the end.
- Off-by-one in the overlap tests. The pruning conditions r < lo and hi < l are exact; flip one inequality and disjoint ranges leak into totals.
Where it is used
- Live range aggregates - leaderboards, monitoring dashboards - where values update constantly and range questions never stop coming.
- Competitive programming's workhorse: range minimum, range sum, k-th element, and with lazy propagation, whole-range updates in O(log n).
- Range-minimum queries inside other algorithms - lowest common ancestor reduces to exactly this kind of query.
- Interval problems in computational geometry, like measuring the union of rectangles during a sweep.
Frequently asked questions
What is the time and space complexity of a segment tree?
Query and update are both O(log n) worst case: any query range splits into O(log n) canonical nodes, and an update recomputes one root-to-leaf path. Space is O(4n) - the standard array allocation that safely holds the recursive layout whatever n is, power of two or not.
What is the difference between a segment tree and a Fenwick tree?
A Fenwick tree stores prefix aggregates in one array - half the code, half the memory - but its range queries subtract one prefix from another, which demands an invertible operation. A segment tree stores every canonical range outright, so min, max, and gcd work directly, and lazy propagation adds range updates on top.
When should I use a segment tree instead of a prefix sum array?
When the data changes. On static data a prefix sum is unbeatable: O(n) build, then O(1) per range sum. But one update forces it to rebuild an O(n) tail, while a segment tree pays O(log n) for the update and O(log n) for every query. The crossover is precisely whether updates happen.
Why does a segment tree need 4n space?
The numbering scheme - children of node i at 2i and 2i+1 - needs a complete tree to avoid collisions. Rounding n up to the next power of two can nearly double the leaf row, and the internal nodes add as many slots again. 4n covers the worst case with one fixed allocation.