A segment tree is a binary tree built over an array so that any range query — sum, minimum, maximum, or a similar aggregate over a subrange — can be answered in O(log n) time, and any single-element update only touches O(log n) nodes to stay correct. It exists for one situation: an array that changes over time, where you also need fast answers to range-aggregate queries. It sits alongside union-find as one of the classic structures for problems that mix queries with updates.
What changed in 2026
- It remains a deliberately old, deliberately stable idea. The core structure has not needed to change — this is a case where a decades-old design is still the right default for the problem it solves.
- Iterative, array-based implementations are now the common default. Recursive pointer-based segment trees are easier to explain, but most production code now builds the tree as a flat array for better cache behavior.
- Persistent variants show up more in real systems. Versioned range queries borrow segment tree ideas, and that pattern has spread from competitive programming into production analytics code.
How a segment tree is built
Each leaf represents one array element. Each internal node represents the aggregate (sum, min, whatever operation you chose) of its two children, recursively, all the way up to a root that represents the aggregate of the entire array. Building it is a single recursive pass:
def build(arr, tree, node, start, end):
if start == end:
tree[node] = arr[start]
return
mid = (start + end) // 2
build(arr, tree, 2 * node, start, mid)
build(arr, tree, 2 * node + 1, mid + 1, end)
tree[node] = tree[2 * node] + tree[2 * node + 1] # combine step
The combine step on the last line is the only part that changes for min, max, or gcd instead of sum.
Range queries in O(log n)
A query for range [L, R] walks the tree and only descends into a subtree that partially overlaps the requested range. Subtrees fully inside return their precomputed aggregate immediately; subtrees fully outside return a neutral value (zero for sum, infinity for min). Because the tree has height O(log n), the whole query stays O(log n) instead of scanning the array.
Updates without a rebuild
Changing one array element means updating that leaf and then walking back up, recomputing each ancestor's aggregate from its two children. That is O(log n) nodes touched, never the whole tree.
How it compares to the alternatives
| Structure |
Range query |
Point update |
Range update |
Best for |
| Plain array |
O(n) |
O(1) |
O(n) |
Small or rarely-queried data |
| Prefix sum array |
O(1) |
O(n) to fix all sums |
O(n) |
Static data, no updates after setup |
| Fenwick tree (BIT) |
O(log n) |
O(log n) |
O(log n) with a trick |
Sum-like invertible operations, simpler code |
| Segment tree |
O(log n) |
O(log n) |
O(log n) with lazy propagation |
Min/max/gcd or anything non-invertible |
If the only operation you need is sum, a Fenwick tree does the same job with less code. Reach for a full segment tree when you need range minimum, maximum, or an operation that cannot be undone by subtraction.
Lazy propagation for range updates
Updating every element in a range one at a time defeats the purpose of a fast structure. Lazy propagation fixes this by marking a subtree as "pending an update" without pushing it down to its children immediately — the push only happens the next time that subtree is visited. This keeps range updates at O(log n) instead of O(n).
Common mistakes
Reaching for a segment tree before checking if the data ever changes. If it does not, a prefix-sum array answers the same queries in O(1) with far less code.
Using a segment tree for sum only, ignoring the simpler Fenwick tree. Both hit O(log n), but the Fenwick tree is shorter and easier to get right under pressure.
Forgetting lazy propagation and updating ranges element by element. This silently turns an O(log n) operation back into an O(n) one, often only surfacing once inputs get large.
FAQ
Is a segment tree the same as a binary search tree?
No. A binary search tree orders elements by value for fast lookup. A segment tree is organized by array position, not value, and is built for range aggregates.
When should I use a Fenwick tree instead?
When the operation is invertible, like sum, and you want less code with the same O(log n) guarantees. Fenwick trees do not naturally support min or max.
Does a segment tree need the array size to be a power of two?
No, though some simple array-based implementations size the underlying array generously to make the indexing math cleaner. It works correctly for any size.
Is a segment tree worth building for a one-off script?
Rarely. It pays off when there are many interleaved queries and updates. For a single pass over static data, simpler structures are faster to write and just as fast to run.
Where to go next