Introduction to Segment Trees
The segment tree exists to solve one specific tension. Let’s make it concrete before we build anything.
The problem: range queries on a mutable array
You’re given an array and a stream of two kinds of operations, interleaved:
- Query
(i, j)→ the aggregate (say, sum) ofarr[i..j]. - Update
(i, v)→ setarr[i] = v.
How fast can you serve both? Consider the two obvious approaches:
| Approach | Query (i,j) | Update (i,v) | Problem |
|---|---|---|---|
| Plain array | O(n) — loop and add | O(1) — assign | queries are slow |
| Prefix-sum array | O(1) — P[j+1] − P[i] | O(n) — rebuild all prefixes after i | updates are slow |
Prefix sums are wonderful for a static array — but the moment a value changes, every prefix after it is wrong, so you re-derive O(n) of the table. If queries and updates are both frequent, both naive approaches degrade to O(n) per operation. Over q operations that’s O(n·q) — too slow when both are large.
The segment tree’s promise: O(log n) for both query and update. It does this by storing partial aggregates in a tree, so a query stitches together a handful of pre-computed pieces, and an update fixes only the pieces that actually contain the changed element. Neither operation ever touches more than O(log n) nodes.
The idea: a tree of ranges
Build a binary tree over the array where:
- The root owns the whole range
[0, n−1]and stores its aggregate. - Each internal node splits its range in half and has two children for the halves.
- The leaves are the individual array elements (range
[i, i]). - Every internal node’s value is combined from its two children (for sum:
node = left + right).
There are only about 2n nodes total (n leaves + n−1 internal), and the tree’s height is ⌈log₂ n⌉. That height is why everything is logarithmic.
Why query is O(log n): the decomposition
To answer sum(i, j), you don’t visit every leaf in the range. Instead you find the smallest set of nodes whose ranges exactly tile [i, j]. Recursing from the root, each node falls into one of three cases:
Fully inside [i, j] → take it whole
The node’s entire range is within the query. Return its stored aggregate — no need to go deeper. This is where the speedup lives.
Fully outside [i, j] → ignore it
No overlap. Return the identity (0 for sum, +∞ for min). Prune the whole subtree.
Partially overlapping → recurse into both children
Split the question across the two halves and combine the results.
It turns out at most O(log n) nodes are ever taken “whole” — the query range is covered by a logarithmic number of canonical segments. Try it on the next page and watch how few nodes light up.
Why update is O(log n): one path
To set arr[i] = v, only the nodes whose range contains i are affected — and those nodes form a single root-to-leaf path (length = height = O(log n)). Update the leaf, then walk back up recomputing each ancestor from its (now-updated) children. Every other node is untouched.
The aggregate must be associative for the tree to work. Combining children into a parent (combine(left, right)) has to be associative so that the order of merging doesn’t change the answer — sum, min, max, gcd, bitwise OR/AND, and matrix product all qualify. Operations like “the median” or “count of distinct elements” are not associative on partial ranges, so they don’t fit a vanilla segment tree. Always ask: can I combine two adjacent partial answers into one? If not, a segment tree won’t help.
Segment tree vs the alternatives
| Structure | Range query | Point update | Range update | Notes |
|---|---|---|---|---|
| Prefix sums | O(1) | O(n) | O(n) | static arrays only |
| Segment tree | O(log n) | O(log n) | O(log n) (lazy) | most general; any associative op |
| Fenwick / BIT | O(log n) | O(log n) | O(log n)† | smaller & faster, but sum/prefix-oriented |
| Sqrt decomposition | O(√n) | O(1) | O(√n) | simpler to code, worse asymptotics |
† BIT range updates need the difference-array trick — covered on the Fenwick page.
The segment tree is the most general; the Fenwick tree is the leaner specialist for prefix sums. Know both and when to pick each.
Quick check
Next: The Template — build, query, update in full code, with an interactive tree that lights up the nodes each operation touches.