7.20 Segment Trees
Segment trees are among the most versatile range-query data structures in algorithm design.
7.20 Segment Trees
Segment trees are among the most versatile range-query data structures in algorithm design.
A prefix-sum array answers static range-sum queries efficiently, but updates are expensive. A Fenwick tree supports dynamic sums, but its capabilities are somewhat specialized. Segment trees generalize the idea by storing information about intervals rather than individual values.
This seemingly simple idea allows a segment tree to answer a wide variety of range queries:
- Sum
- Minimum
- Maximum
- Greatest common divisor
- Bitwise operations
- Frequency counts
- Custom associative aggregates
while supporting efficient updates.
For this reason, segment trees appear frequently in competitive programming, analytics systems, monitoring platforms, numerical computing, and database internals.
Problem
Given an array:
[2, 4, 5, 7, 8, 10]
support operations such as:
Range sum
Range minimum
Range maximum
and allow values to change.
Example:
Update index 2 to value 20
A direct scan answers queries in:
O(n)
A prefix-sum array answers sums in:
O(1)
but updates require:
O(n)
We want both queries and updates to remain efficient.
Solution
Store information about intervals.
Example array:
[2, 4, 5, 7]
Build a tree:
[0,3]
/ \\n [0,1] [2,3]
/ \ / \\n [0] [1] [2] [3]
Each node stores information about its interval.
For sums:
18
/ \\n 6 12
/ \ / \\n 2 4 5 7
The root represents the entire array.
Every internal node combines information from its children.
Understanding the Structure
Each node corresponds to a range.
Example:
Array:
Index: 0 1 2 3
Value: 2 4 5 7
Tree:
[0,3]
├── [0,1]
│ ├── [0,0]
│ └── [1,1]
└── [2,3]
├── [2,2]
└── [3,3]
The leaves correspond to individual elements.
Internal nodes summarize larger intervals.
This hierarchical decomposition enables logarithmic operations.
Node Representation
Conceptually:
type SegmentTree struct {
tree []int
n int
}
Most implementations store the tree in an array.
For:
n elements
allocating:
4 * n
positions is usually sufficient.
This avoids explicit pointer structures and improves cache locality.
Building the Tree
Construction recursively divides intervals.
func (st *SegmentTree) build(
nums []int,
node int,
left int,
right int,
) {
if left == right {
st.tree[node] = nums[left]
return
}
mid := left + (right-left)/2
st.build(
nums,
node*2,
left,
mid,
)
st.build(
nums,
node*2+1,
mid+1,
right,
)
st.tree[node] =
st.tree[node*2] +
st.tree[node*2+1]
}
Each node combines its children's values.
For sum queries:
parent = left + right
Other query types use different combine operations.
Building Example
Array:
[2, 4, 5, 7]
Leaves:
2
4
5
7
Parents:
6
12
Root:
18
The tree stores:
sum([0,1]) = 6
sum([2,3]) = 12
sum([0,3]) = 18
These precomputed summaries make future queries efficient.
Range Sum Query
Suppose:
Query:
[1,3]
Desired result:
4 + 5 + 7 = 16
The query recursively examines only relevant nodes.
Nodes fully inside the range contribute immediately.
Nodes completely outside the range contribute nothing.
This selective traversal is the key optimization.
Query Cases
Every node falls into one of three categories.
Completely Outside
Node interval:
[0,1]
Query:
[2,3]
No overlap.
Return:
0
Completely Inside
Node interval:
[2,3]
Query:
[2,3]
Full overlap.
Return stored value immediately.
Partial Overlap
Node interval:
[0,3]
Query:
[1,2]
Must recurse into both children.
Combine results afterward.
These three cases appear in nearly every segment-tree implementation.
Query Implementation
func (st *SegmentTree) query(
node int,
start int,
end int,
left int,
right int,
) int {
if right < start ||
end < left {
return 0
}
if left <= start &&
end <= right {
return st.tree[node]
}
mid := start + (end-start)/2
return st.query(
node*2,
start,
mid,
left,
right,
) +
st.query(
node*2+1,
mid+1,
end,
left,
right,
)
}
The recursion naturally follows interval boundaries.
Example Query Walkthrough
Array:
[2, 4, 5, 7]
Query:
[1,3]
Tree:
[0,3]
/ \\n [0,1] [2,3]
The root partially overlaps.
Visit both children.
[0,1]
partially overlaps.
Visit its children.
[0,0]
outside.
Ignore.
[1,1]
inside.
Use value:
4
The entire:
[2,3]
interval is inside.
Use stored value:
12
Result:
4 + 12 = 16
No unnecessary nodes are examined.
Point Updates
Suppose:
Index 2
changes from:
5
to:
20
Only one root-to-leaf path changes.
Updated tree:
33
/ \\n 6 27
/ \ / \\n 2 4 20 7
The update affects only:
[2]
[2,3]
[0,3]
All other nodes remain unchanged.
Update Implementation
func (st *SegmentTree) update(
node int,
start int,
end int,
index int,
value int,
) {
if start == end {
st.tree[node] = value
return
}
mid := start + (end-start)/2
if index <= mid {
st.update(
node*2,
start,
mid,
index,
value,
)
} else {
st.update(
node*2+1,
mid+1,
end,
index,
value,
)
}
st.tree[node] =
st.tree[node*2] +
st.tree[node*2+1]
}
Only logarithmically many nodes require recomputation.
Range Minimum Query
Segment trees are not limited to sums.
Suppose:
[7, 2, 5, 3, 6]
Store:
minimum
instead of:
sum
Parent computation becomes:
min(left, right)
The structure remains unchanged.
Only the aggregation operation changes.
Query:
[1,4]
returns:
2
in logarithmic time.
Range Maximum Query
Replace:
min(left, right)
with:
max(left, right)
The tree now answers maximum queries.
Example:
[7, 2, 5, 3, 6]
Query:
[1,4]
Result:
6
Again:
O(log n)
query time.
Associative Operations
Segment trees require an associative operation.
(a op b) op c
=
a op (b op c)
Examples:
sum
minimum
maximum
gcd
lcm
bitwise and
bitwise or
Because the operation is associative, interval summaries can be combined correctly.
This property makes segment trees highly general.
Lazy Propagation
Some problems update entire ranges.
Example:
Add 5 to every element
between indices 100 and 500
Updating each element individually costs:
O(n)
Lazy propagation postpones updates until they become necessary.
The tree stores pending modifications and applies them only when affected nodes are visited.
This optimization enables:
Range updates
Range queries
both in:
O(log n)
time.
Lazy propagation is one of the most important advanced segment-tree techniques.
Segment Trees Versus Fenwick Trees
| Feature | Segment Tree | Fenwick Tree |
|---|---|---|
| Sum queries | Yes | Yes |
| Min/Max queries | Yes | Limited |
| Custom aggregates | Yes | Difficult |
| Range updates | Yes | More complex |
| Memory usage | Higher | Lower |
| Implementation | More complex | Simpler |
Fenwick trees excel for sums.
Segment trees excel for generality.
Segment Trees Versus Prefix Sums
| Feature | Prefix Sum | Segment Tree |
|---|---|---|
| Query | O(1) | O(log n) |
| Update | O(n) | O(log n) |
| Dynamic data | Poor | Excellent |
| Simplicity | Excellent | Moderate |
For static data, prefix sums are often preferable.
For dynamic data, segment trees are far more flexible.
Real-World Applications
Segment trees appear in:
- Monitoring systems
- Financial analytics
- Time-series databases
- Computational geometry
- Network telemetry
- Scientific simulations
- Competitive programming
Any application involving repeated interval aggregation is a candidate.
Complexity Analysis
For:
n elements
Build:
O(n)
Query:
O(log n)
Update:
O(log n)
Space:
O(n)
More precisely:
O(4n)
for the array representation.
The constant factor is modest and predictable.
Common Mistakes
A common mistake is using segment trees when a simpler prefix-sum solution is sufficient. Segment trees are powerful but add implementation complexity.
Another mistake is forgetting the three overlap cases during query processing. Incorrect overlap handling often produces subtle bugs.
A third mistake is selecting a non-associative aggregation function. Without associativity, interval summaries cannot be combined reliably.
Finally, many implementations overlook lazy propagation when range updates become frequent, leading to avoidable performance problems.
Takeaway
Segment trees transform arrays into hierarchical interval summaries. By storing aggregate information for recursively partitioned ranges, they support logarithmic-time queries and updates while remaining flexible enough for a wide variety of operations. Their power comes from decomposing a large range into a small collection of precomputed intervals whose results can be combined efficiently. This ability to summarize and update intervals makes segment trees one of the most important range-query structures in algorithm design.