7.19 Range Queries
A range query asks for information about a contiguous region of ordered data.
7.19 Range Queries
A range query asks for information about a contiguous region of ordered data.
Sometimes the query returns the elements themselves. More often, it returns an aggregate: a count, sum, minimum, maximum, average, or other summary over a range.
Examples:
How many values lie between 100 and 500?
What is the sum of sales from day 20 to day 30?
What is the minimum latency between timestamps t1 and t2?
Which orders were created in this time window?
Binary search helps locate range boundaries. Ordered data structures make those boundaries efficient to maintain under updates. Specialized range-query structures go further by storing summaries inside the data structure, allowing many range queries to run in logarithmic time.
Problem
Given an array:
[2, 4, 5, 7, 8, 10, 13]
answer queries such as:
Sum from index 2 to index 5
Minimum from index 1 to index 4
Count values between 5 and 10
A direct scan works:
func RangeSumLinear(nums []int, left, right int) int {
sum := 0
for i := left; i <= right; i++ {
sum += nums[i]
}
return sum
}
For one query, this may be acceptable.
For many queries, linear scanning becomes expensive.
Solution
Choose a structure based on the update pattern and query type.
| Structure | Best For | Query | Update |
|---|---|---|---|
| Prefix sum | Static range sums | O(1) | O(n) |
| Fenwick tree | Dynamic prefix sums | O(log n) | O(log n) |
| Segment tree | Dynamic range aggregates | O(log n) | O(log n) |
| Ordered map | Dynamic key ranges | O(log n + k) | O(log n) |
| B-tree | Large persisted ranges | O(log n + k) | O(log n) |
The right structure depends on whether data changes and which aggregate is required.
Static Range Sum with Prefix Sums
If the array does not change, prefix sums are the simplest solution.
Given:
nums = [2, 4, 5, 7, 8]
Build:
prefix[0] = 0
prefix[1] = 2
prefix[2] = 6
prefix[3] = 11
prefix[4] = 18
prefix[5] = 26
Then:
sum(left, right) = prefix[right + 1] - prefix[left]
Implementation:
func BuildPrefix(nums []int) []int {
prefix := make([]int, len(nums)+1)
for i, v := range nums {
prefix[i+1] = prefix[i] + v
}
return prefix
}
func RangeSum(prefix []int, left, right int) int {
return prefix[right+1] - prefix[left]
}
Example:
nums := []int{2, 4, 5, 7, 8}
prefix := BuildPrefix(nums)
fmt.Println(RangeSum(prefix, 1, 3))
Output:
16
because:
4 + 5 + 7 = 16
Range Counting with Bounds
If the values are sorted, binary search answers count queries.
Given:
[1, 3, 4, 4, 4, 6, 8, 9, 11]
Count values in:
[4, 8]
Compute:
count := UpperBound(nums, 8) - LowerBound(nums, 4)
Result:
5
The matching values are:
4, 4, 4, 6, 8
This query takes logarithmic time.
No scan is needed unless the values themselves must be returned.
Dynamic Range Sum with Fenwick Trees
Prefix sums fail when values change frequently.
If one element changes, many prefix entries must be updated.
A Fenwick tree, also called a binary indexed tree, supports:
Point update: O(log n)
Prefix sum: O(log n)
Range sum: O(log n)
The idea is to store partial sums in a compact indexed structure.
type Fenwick struct {
tree []int
}
func NewFenwick(n int) *Fenwick {
return &Fenwick{
tree: make([]int, n+1),
}
}
Update:
func (f *Fenwick) Add(index, delta int) {
index++
for index < len(f.tree) {
f.tree[index] += delta
index += index & -index
}
}
Prefix sum:
func (f *Fenwick) PrefixSum(index int) int {
index++
sum := 0
for index > 0 {
sum += f.tree[index]
index -= index & -index
}
return sum
}
Range sum:
func (f *Fenwick) RangeSum(left, right int) int {
if left == 0 {
return f.PrefixSum(right)
}
return f.PrefixSum(right) -
f.PrefixSum(left-1)
}
Fenwick trees are compact and fast for sum-like operations.
Dynamic Aggregates with Segment Trees
Segment trees support more general range queries.
They can store:
sum
minimum
maximum
gcd
custom associative aggregates
A segment tree recursively partitions the array.
Example:
[2, 4, 5, 7]
Tree:
[0,3]
/ \\n [0,1] [2,3]
/ \ / \\n [0] [1] [2] [3]
Each internal node stores an aggregate over its range.
For sums:
18
/ \\n 6 12
/ \ / \\n 2 4 5 7
Querying a range combines only the nodes that fully cover pieces of the query interval.
Segment Tree Query
A minimal recursive range-sum query:
type SegmentTree struct {
tree []int
n int
}
func NewSegmentTree(nums []int) *SegmentTree {
st := &SegmentTree{
tree: make([]int, 4*len(nums)),
n: len(nums),
}
st.build(nums, 1, 0, len(nums)-1)
return st
}
func (st *SegmentTree) build(
nums []int,
node, left, 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]
}
Query:
func (st *SegmentTree) Query(left, right int) int {
return st.query(1, 0, st.n-1, left, right)
}
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)
}
This answers range sums in logarithmic time.
Point Updates in Segment Trees
To update one value, update the leaf and then recompute its ancestors.
func (st *SegmentTree) Update(index, value int) {
st.update(1, 0, st.n-1, index, value)
}
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 one path from root to leaf changes.
The update cost is:
O(log n)
Ordered Key Range Queries
When data is keyed by values rather than positions, ordered maps become useful.
Example:
timestamp -> event
price -> product
score -> document
A range query over keys uses lower bound and iteration.
Find first key >= start.
Iterate until key > end.
Cost:
O(log n + k)
where k is the number of returned entries.
This is the typical model used by B-trees, red-black trees, skip lists, and many database indexes.
Range Minimum Queries
Range minimum queries ask for the smallest value inside an interval.
Example:
nums = [7, 2, 5, 3, 6]
query [1, 3]
answer = 2
A segment tree handles this by changing the combine operation.
Instead of:
a + b
use:
min(a, b)
The structure remains the same.
Only the aggregate changes.
This is a recurring theme in range-query structures: once the decomposition is built, many associative operations fit naturally.
Associativity Requirement
Segment trees work well when the aggregate operation is associative.
That means:
(a op b) op c = a op (b op c)
Examples:
sum
min
max
gcd
bitwise and
bitwise or
Non-associative operations are harder because partial results cannot be safely combined in arbitrary grouping.
This requirement determines whether a segment tree is appropriate.
Choosing the Right Structure
Use prefix sums when:
The array is static.
The query is range sum.
Use Fenwick trees when:
You need point updates and prefix/range sums.
Use segment trees when:
You need dynamic range aggregates beyond simple sums.
Use ordered maps or B-trees when:
The query is over sorted keys rather than array positions.
The wrong choice often leads to unnecessary complexity or poor performance.
Complexity Analysis
| Structure | Build | Query | Update |
|---|---|---|---|
| Prefix sum | O(n) | O(1) | O(n) |
| Fenwick tree | O(n log n) or O(n) | O(log n) | O(log n) |
| Segment tree | O(n) | O(log n) | O(log n) |
| Ordered map | O(n log n) | O(log n + k) | O(log n) |
| B-tree | O(n log n) | O(log n + k) | O(log n) |
For returned records, the k term is unavoidable because the output itself has size k.
Common Mistakes
A common mistake is using prefix sums for mutable data. Once updates become frequent, prefix sums lose their advantage.
Another mistake is using a segment tree for a problem that only needs static range sums. Prefix sums are simpler and faster.
A third mistake is forgetting the output cost in range retrieval queries. Even if boundaries are found in logarithmic time, returning one million matching records still costs one million steps.
Finally, many implementations use inclusive and exclusive boundaries inconsistently. Pick one convention and apply it throughout.
Takeaway
Range queries generalize binary search from locating a single position to answering questions over intervals. For static sums, prefix arrays provide constant-time queries. For mutable sums, Fenwick trees give logarithmic updates and queries. For more general aggregates, segment trees provide a flexible framework. For ordered key ranges, balanced trees, skip lists, and B-trees locate boundaries and scan results efficiently. The central design question is always the same: what is being queried, what changes, and what structure preserves enough information to answer quickly?