8.13 Segment Trees
Many tree algorithms eventually become range-query problems.
8.13 Segment Trees
Many tree algorithms eventually become range-query problems.
After applying an Euler Tour, a subtree becomes a contiguous interval. Once that transformation is complete, the original tree often disappears from the solution. What remains is a sequence of values and a collection of interval operations.
Examples include:
- Sum of values in a subtree
- Maximum value in a subtree
- Minimum value in a subtree
- Frequency counts
- Dynamic updates
- Range assignments
Prefix sums solve some of these problems, but they fail when updates occur frequently.
Segment Trees provide a general framework for efficient range queries and updates. They are among the most important data structures in algorithm design and appear repeatedly throughout advanced tree algorithms.
Problem
You need efficient range queries and updates on a sequence of values.
Examples:
Query:
sum(100, 500)
Update:
value[237] += 10
A naive solution scans the range every time.
For large datasets, this becomes too expensive.
Solution
Store aggregate information in a balanced binary tree.
Consider the array:
Index: 0 1 2 3 4 5 6 7
Value: 5 2 7 1 4 3 8 6
A Segment Tree recursively divides the array.
[0,7]
/ \\n [0,3] [4,7]
/ \ / \\n [0,1] [2,3] [4,5] [6,7]
Each node stores information about its interval.
For a sum tree:
node value =
sum of interval
The root stores:
5+2+7+1+4+3+8+6 = 36
Queries examine only relevant intervals.
Updates modify only affected paths.
Discussion
The central idea is divide and conquer.
Suppose we need:
sum(2,6)
Instead of examining every element:
7+1+4+3+8
the Segment Tree combines precomputed intervals.
[2,3]
+
[4,5]
+
[6,6]
Only a small portion of the structure is visited.
This is why queries become logarithmic.
Building the Tree
A simple recursive implementation:
package main
type SegmentTree struct {
tree []int
n int
}
func NewSegmentTree(
values []int,
) *SegmentTree {
n := len(values)
st := &SegmentTree{
tree: make([]int, 4*n),
n: n,
}
st.build(
values,
1,
0,
n-1,
)
return st
}
The factor:
4*n
provides enough space for the internal tree representation.
Build recursively:
func (st *SegmentTree) build(
values []int,
node int,
left int,
right int,
) {
if left == right {
st.tree[node] = values[left]
return
}
mid := (left + right) / 2
st.build(
values,
node*2,
left,
mid,
)
st.build(
values,
node*2+1,
mid+1,
right,
)
st.tree[node] =
st.tree[node*2] +
st.tree[node*2+1]
}
Each internal node stores the sum of its children.
Range Sum Query
Querying follows the tree structure.
Three cases exist.
No Overlap
Query: [5,7]
Node : [0,3]
The intervals do not intersect.
Contribution:
0
Complete Overlap
Query: [2,5]
Node : [2,5]
The interval is entirely contained.
Return the stored value immediately.
Partial Overlap
The interval must be split into children.
Implementation:
func (st *SegmentTree) query(
node int,
left int,
right int,
ql int,
qr int,
) int {
if qr < left || right < ql {
return 0
}
if ql <= left &&
right <= qr {
return st.tree[node]
}
mid := (left + right) / 2
return st.query(
node*2,
left,
mid,
ql,
qr,
) +
st.query(
node*2+1,
mid+1,
right,
ql,
qr,
)
}
Public interface:
func (st *SegmentTree) Sum(
left int,
right int,
) int {
return st.query(
1,
0,
st.n-1,
left,
right,
)
}
Point Updates
Suppose:
value[3] = 10
Only intervals containing index 3 change.
Update recursively:
func (st *SegmentTree) update(
node int,
left int,
right int,
index int,
value int,
) {
if left == right {
st.tree[node] = value
return
}
mid := (left + right) / 2
if index <= mid {
st.update(
node*2,
left,
mid,
index,
value,
)
} else {
st.update(
node*2+1,
mid+1,
right,
index,
value,
)
}
st.tree[node] =
st.tree[node*2] +
st.tree[node*2+1]
}
Only one root-to-leaf path is updated.
Complexity remains logarithmic.
Maximum Queries
Segment Trees are not limited to sums.
Replace:
st.tree[node*2] +
st.tree[node*2+1]
with:
max(
st.tree[node*2],
st.tree[node*2+1],
)
Now the structure answers:
maximum(left,right)
queries.
The overall algorithm remains unchanged.
Only the aggregation operation changes.
Minimum Queries
Similarly:
min(
st.tree[node*2],
st.tree[node*2+1],
)
creates a minimum Segment Tree.
This flexibility is one reason Segment Trees are so widely used.
Any associative operation can often be supported.
Examples include:
- Sum
- Minimum
- Maximum
- Greatest common divisor
- Bitwise AND
- Bitwise OR
Segment Trees and Euler Tour
Tree algorithms frequently combine Euler Tour with Segment Trees.
Suppose:
Subtree(1)
corresponds to:
[4,12]
in Euler order.
The query:
Sum of subtree(1)
becomes:
segmentTree.Sum(4,12)
The original tree never appears in the query.
Euler Tour transforms:
Tree Query
into:
Range Query
Segment Trees answer the range query efficiently.
This combination appears throughout modern tree algorithms.
Iterative Segment Trees
Recursive implementations are intuitive.
High-performance systems often use iterative versions.
Store leaves in the second half of an array:
tree[n]
tree[n+1]
...
tree[2n-1]
Build upward:
for i := n - 1; i > 0; i-- {
tree[i] =
tree[i*2] +
tree[i*2+1]
}
Advantages:
- Better cache locality
- No recursion
- Smaller constant factors
Competitive programmers often prefer iterative implementations.
The underlying principles remain identical.
Why Segment Trees Work
A useful mental model is:
Precompute answers
for every important interval.
The tree stores information for:
[0,7]
[0,3]
[4,7]
[0,1]
[2,3]
...
Most queries can be assembled from a small number of these intervals.
This avoids scanning the original data repeatedly.
The same principle appears in:
- Sparse Tables
- Binary Lifting
- Fenwick Trees
- Dynamic Programming
Precompute once, reuse many times.
Complexity Analysis
Let:
n = number of elements
Building:
| Operation | Complexity |
|---|---|
| Build tree | O(n) |
Queries:
| Operation | Complexity |
|---|---|
| Range query | O(log n) |
Updates:
| Operation | Complexity |
|---|---|
| Point update | O(log n) |
Memory:
| Structure | Complexity |
|---|---|
| Segment Tree | O(n) |
The memory constant is larger than arrays or Fenwick Trees, but the flexibility is significantly greater.
Segment Tree vs Fenwick Tree
| Feature | Fenwick Tree | Segment Tree |
|---|---|---|
| Range sums | Excellent | Excellent |
| Point updates | O(log n) | O(log n) |
| Range minimum | Difficult | Natural |
| Range maximum | Difficult | Natural |
| Custom aggregates | Limited | Flexible |
| Memory | Smaller | Larger |
| Implementation | Simpler | More complex |
Fenwick Trees excel when sums are the only requirement.
Segment Trees support a broader range of operations.
Common Mistakes
A common mistake is using:
mid = (left + right) / 2
incorrectly and creating overlapping intervals.
The two child intervals should be:
[left, mid]
[mid+1, right]
Another mistake is forgetting the no-overlap case.
Without it, recursion continues unnecessarily and produces incorrect results.
A third mistake is choosing the wrong neutral element.
For sum queries:
0
is correct.
For maximum queries:
-∞
is required.
For minimum queries:
+∞
is required.
Using the wrong identity element often produces subtle bugs.
Finally, many implementations allocate only:
2*n
elements for recursive trees. While this sometimes works, the standard recursive implementation generally allocates:
4*n
to avoid overflow.
Takeaway
Segment Trees store aggregate information for intervals and answer range queries efficiently. By recursively partitioning the data, they reduce many operations from linear time to logarithmic time. Combined with Euler Tours, they become one of the most powerful tools for subtree processing, allowing complex tree queries to be transformed into ordinary range operations on arrays.