Range Queries: Prefix Sums, Sparse Tables, Fenwick and Segment Trees
After this lesson, you will be able to:
- State the range query problem and the three costs that matter: build, query and update
- Explain why prefix sums answer sums in O(1) but make every update cost O(n)
- Build a sparse table, answer a range minimum in two lookups, and say why it fails for sums
- Explain the lowbit trick, trace a Fenwick update and prefix query by hand, and prove each takes O(log n) passes
- Write a segment tree with build, point update and range query, and argue why a query visits about 4 log n nodes
- Describe lazy propagation and sqrt decomposition, and pick the right structure from a decision table
Before You Start
#The Range Query Problem
position: 0 1 2 3 4 5 6 7
value: 5 2 7 3 9 1 6 4
The plain way is a loop over the range for every query. That costs O(n) per query, so q queries cost O(n q). With n and q both at 100,000, that is 10,000,000,000 steps. The loop is not wrong, only too slow.
#Prefix Sums, and Where They Stop
prefix holds at each place the total of everything before it, starting with a 0. The sum of positions l to r is prefix[r + 1] - prefix[l], one subtraction. Build costs O(n) time and O(n) space. A query costs O(1).from itertools import accumulate
a = [5, 2, 7, 3, 9, 1, 6, 4]
prefix = [0] + list(accumulate(a))
print(prefix)
print("sum of a[2..4]:", prefix[5] - prefix[2])
# Output:
# [0, 5, 7, 14, 17, 26, 27, 33, 37]
# sum of a[2..4]: 19Now let one value change. Each prefix cell holds the total of everything before it, so a change at position 2 must reach every cell after it.
a[2] += 10 # one value changes
new_prefix = [0] + list(accumulate(a))
changed = sum(1 for x, y in zip(prefix, new_prefix) if x != y)
print("prefix cells that changed:", changed, "of", len(prefix))
a[2] -= 10 # put it back
# Output:
# prefix cells that changed: 6 of 9Six of nine cells changed, and the count grows with n: a change near the front rewrites almost the whole list. So an update costs O(n). Prefix sums are perfect when the data never changes, and weak when it does.
Prefix sums also lean on one property: the operation must be invertible, because the answer comes from subtracting. They cannot answer a range minimum at all. The total before position l is a minimum of the wrong stretch, and nothing lets us take the left part back out.
Here are the two ends of the line. A plain loop has update O(1) and query O(n). Prefix sums have query O(1) and update O(n). A good structure should land in the middle, with both near O(log n). The Fenwick tree and the segment tree do exactly that. First, a detour for the case that never changes.
#Sparse Table: Static Range Minimum
Suppose the array is fixed and we need minimums. Subtraction is no help, so use the idempotent property instead. The key picture: any range of length m is covered by two blocks of length 2^k, where 2^k is the biggest power of two not above m. The two blocks may overlap, and for a minimum the overlap does no harm, because taking the minimum of a value twice gives the same answer.
Our array of 8 gives these rows. Row 1 holds the minimum of every pair, row 2 of every four, row 3 of all eight.
def build_sparse(values):
"""Row j holds the minimum of every block of length 2**j. O(n log n) time and space."""
table = [list(values)]
j = 1
while (1 << j) <= len(values):
prev = table[-1]
half = 1 << (j - 1)
table.append([min(prev[i], prev[i + half]) for i in range(len(values) - (1 << j) + 1)])
j += 1
return table
def sparse_min(table, left, right):
"""Minimum of values[left..right], both ends included. Two lookups, so O(1)."""
k = (right - left + 1).bit_length() - 1 # biggest power of two that fits
return min(table[k][left], table[k][right - (1 << k) + 1])
table = build_sparse(a)
for row in table:
print(row)
print(sparse_min(table, 2, 6), sparse_min(table, 0, 7), sparse_min(table, 3, 3))
# Output:
# [5, 2, 7, 3, 9, 1, 6, 4]
# [2, 2, 3, 3, 1, 1, 4]
# [2, 2, 1, 1, 1]
# [1]
# 1 1 3Try one query by hand before reading how it works.
Ask for the minimum of positions 2 to 6, a range of length 5. The biggest power of two that fits in 5 is 4. A sparse table answers with two blocks of length 4. At which start positions do the two blocks begin?
bit_length, which is the position of the top bit, a trick from Bit Manipulation. A length of 5 is 101 in binary, which has 3 bits, so k is 2. The two blocks are [7, 3, 9, 1] and [3, 9, 1, 6]. The table stores 1 as the minimum of both, so the answer is 1.bit_length, so O(1). That is the best query cost of any structure in this lesson.#Fenwick Tree: Sums With Updates
i & -i. It keeps only the lowest set bit of i, so it is the value of that bit. For 12, which is 1100 in binary, it is 4. We call it lowbit. The eight values for 1 to 8 are 1, 2, 1, 4, 1, 2, 1, 8.Number the positions from 1, not 0. This is not a taste: lowbit of 0 is 0, and the loops below would never move. The rule is that cell i stores the sum of the lowbit(i) values that end at position i.
| Cell | lowbit | Positions covered | Stored sum |
|---|---|---|---|
| 1 | 1 | 1 | 5 |
| 2 | 2 | 1 to 2 | 7 |
| 3 | 1 | 3 | 7 |
| 4 | 4 | 1 to 4 | 17 |
| 5 | 1 | 5 | 9 |
| 6 | 2 | 5 to 6 | 10 |
| 7 | 1 | 7 | 6 |
| 8 | 8 | 1 to 8 | 37 |
Why does this work? Removing the lowest set bit of i walks left over exactly the stretches in the table. Cell i covers lowbit(i) values, and i minus lowbit(i) is where the next stretch ends. The stretches never overlap and together they cover 1 to i. The number of passes equals the number of 1 bits in i, at most log2 n + 1.
Add 4 to the value at position 5, counting from 1, in the 8-cell tree from the table. Which cells have to change?
The rule that the answer used: start at the position, add lowbit, and repeat until you pass n. From 5, add 1 to get 6, add 2 to get 8, add 8 to get 16 and stop. Each step lands on the next cell that covers the position, because adding lowbit carries the lowest bit upward, so the new cell has a bigger lowbit and its stretch reaches back far enough to include the old one.
This takes O(log n) passes. Every pass at least doubles lowbit, and a cell number never exceeds n, so there are at most floor(log2 n) + 1 passes.
class Fenwick:
"""Sum of a list with point updates. Cell i covers the lowbit(i) values that end at position i."""
def __init__(self, values):
self.n = len(values)
self.tree = [0] * (self.n + 1) # position 0 is unused
self.steps = 0 # counts loop passes, so we can see O(log n)
for i in range(1, self.n + 1): # O(n) build: hand each cell to its parent once
self.tree[i] += values[i - 1]
parent = i + (i & -i)
if parent <= self.n:
self.tree[parent] += self.tree[i]
def add(self, index, delta):
"""Add delta to values[index]. At most about log2(n) + 1 passes."""
i = index + 1 # shift to 1-based
while i <= self.n:
self.tree[i] += delta
i += i & -i # jump to the next cell that covers us
self.steps += 1
def prefix(self, count):
"""Sum of the first count values. One pass per set bit of count."""
total = 0
i = count
while i > 0:
total += self.tree[i]
i -= i & -i # strip the lowest set bit
self.steps += 1
return total
def range_sum(self, left, right):
"""Sum of values[left..right], both ends included."""
return self.prefix(right + 1) - self.prefix(left)
fw = Fenwick(a)
print(fw.tree[1:])
print(fw.range_sum(2, 4), fw.range_sum(0, 7))
fw.steps = 0
fw.add(2, 10)
print("update steps:", fw.steps)
fw.steps = 0
print(fw.range_sum(2, 4), "query steps:", fw.steps)
fw.add(2, -10)
# Output:
# [5, 7, 7, 17, 9, 10, 6, 37]
# 19 37
# update steps: 3
# 29 query steps: 3i + lowbit(i). Each cell is touched once.prefix(r + 1) - prefix(l), so the operation must be invertible. Sum, xor and counting work. Minimum and maximum do not, except in a narrow case: a Fenwick tree can answer prefix minimums if values only ever decrease.A Fenwick tree has 16 cells. You add to position 3 (counting from 1). Which cells does the update loop touch?
#Segment Tree: Any Operation
The picture is a tree of stretches. The root covers the whole array. Each node splits its stretch into a left half and a right half, which are its two children. A leaf covers one value. Each node stores the answer for its stretch, which is the combine of its children's answers. For minimums on our array:
[0..7] min 1
[0..3] min 2 [4..7] min 1
[0..1] 2 [2..3] 3 [4..5] 1 [6..7] 4
5 2 7 3 9 1 6 4
The root is partly inside, so ask both children. Stretch 0 to 3 is partly inside. Its child 0 to 1 is outside, and its child 2 to 3 is inside and returns 3.
Stretch 4 to 7 is partly inside. Its child 4 to 5 is inside and returns 1. Its child 6 to 7 is partly inside, so 6 alone is inside and returns 6, and 7 alone is outside. The answer is the smaller of 3, 1 and 6, which is 1. That visited 9 nodes.
class SegmentTree:
"""Range minimum with point updates. Node k covers a stretch; its children are 2k and 2k + 1."""
def __init__(self, values):
self.n = len(values)
self.tree = [0] * (4 * self.n) # 4n is always enough for the recursive layout
self.visited = 0 # counts nodes touched, to see the cost
self._build(1, 0, self.n - 1, values)
def _build(self, node, lo, hi, values):
if lo == hi:
self.tree[node] = values[lo]
return
mid = (lo + hi) // 2
self._build(2 * node, lo, mid, values)
self._build(2 * node + 1, mid + 1, hi, values)
self.tree[node] = min(self.tree[2 * node], self.tree[2 * node + 1])
def update(self, index, value, node=1, lo=0, hi=None):
"""Set values[index] = value, then repair the minimums on the way back up. O(log n)."""
if hi is None:
hi = self.n - 1
self.visited += 1
if lo == hi:
self.tree[node] = value
return
mid = (lo + hi) // 2
if index <= mid:
self.update(index, value, 2 * node, lo, mid)
else:
self.update(index, value, 2 * node + 1, mid + 1, hi)
self.tree[node] = min(self.tree[2 * node], self.tree[2 * node + 1])
def query(self, left, right, node=1, lo=0, hi=None):
"""Minimum of values[left..right]. O(log n): at most two nodes per level split further."""
if hi is None:
hi = self.n - 1
self.visited += 1
if left <= lo and hi <= right: # this node sits fully inside the question
return self.tree[node]
if right < lo or hi < left: # no overlap at all
return float("inf")
mid = (lo + hi) // 2
return min(self.query(left, right, 2 * node, lo, mid),
self.query(left, right, 2 * node + 1, mid + 1, hi))
st = SegmentTree(a)
print("range 2..6:", st.query(2, 6), "nodes visited:", st.visited)
st.visited = 0
print("range 0..7:", st.query(0, 7), "nodes visited:", st.visited)
st.visited = 0
print("range 4..4:", st.query(4, 4), "nodes visited:", st.visited)
st.visited = 0
st.update(5, 0)
print("update visited:", st.visited, "then range 2..6 is", st.query(2, 6))
# Output:
# range 2..6: 1 nodes visited: 9
# range 0..7: 1 nodes visited: 1
# range 4..4: 9 nodes visited: 7
# update visited: 4 then range 2..6 is 0The whole array is answered by the root alone. A single value takes 7 visits, because the walk goes down a full path and also peeks at the neighbors on the way.
A node that is partly inside the question must contain one of the two ends of the range, and each end lies in only one node per level, so at most two nodes per level are partly inside. Every other node the query touches is a child of a partly inside node and stops at once, either fully inside or fully outside. Two partial nodes have four children at most, so at most 4 nodes are visited per level.
With about log2 n + 1 levels, the total is about 4 log n. On 1,000 values, the largest count the playground run below finds is 39 visits, against a limit of 4 times 10, which is 40.
min with + and the identity with 0, and you have a sum tree. Compared with the Fenwick tree it uses more memory and more code, and its constants are larger. In return it handles minimum, maximum, gcd, and any custom combine.#Lazy Propagation: Updating a Whole Range
amount to a stretch of length m raises the stretch's total by amount * m. The tag holds amount. Before any later operation goes below that node, it pushes the tag down: apply it to both children's totals, add it to their tags, and clear the node's tag. The push costs O(1) per node, and operations only push on the nodes they pass through.A lazy sum tree holds 8 values. You add 5 to every position, 0 to 7. How many nodes does that update visit?
_apply method is the only place that knows what a tag means, so a different operation changes mostly that method.class LazySumTree:
"""Range add and range sum, both in O(log n). A tag means: my children still owe this add."""
def __init__(self, values):
self.n = len(values)
self.total = [0] * (4 * self.n)
self.tag = [0] * (4 * self.n)
self.visited = 0
self._build(1, 0, self.n - 1, values)
def _build(self, node, lo, hi, values):
if lo == hi:
self.total[node] = values[lo]
return
mid = (lo + hi) // 2
self._build(2 * node, lo, mid, values)
self._build(2 * node + 1, mid + 1, hi, values)
self.total[node] = self.total[2 * node] + self.total[2 * node + 1]
def _apply(self, node, lo, hi, amount):
self.total[node] += amount * (hi - lo + 1) # the whole stretch grows by amount each
self.tag[node] += amount # remember it for the children
def _push(self, node, lo, hi):
if self.tag[node]:
mid = (lo + hi) // 2
self._apply(2 * node, lo, mid, self.tag[node])
self._apply(2 * node + 1, mid + 1, hi, self.tag[node])
self.tag[node] = 0
def add(self, left, right, amount, node=1, lo=0, hi=None):
"""Add amount to every value in left..right. O(log n)."""
if hi is None:
hi = self.n - 1
self.visited += 1
if right < lo or hi < left:
return
if left <= lo and hi <= right:
self._apply(node, lo, hi, amount) # stop here, leave the children for later
return
self._push(node, lo, hi)
mid = (lo + hi) // 2
self.add(left, right, amount, 2 * node, lo, mid)
self.add(left, right, amount, 2 * node + 1, mid + 1, hi)
self.total[node] = self.total[2 * node] + self.total[2 * node + 1]
def query(self, left, right, node=1, lo=0, hi=None):
"""Sum of values[left..right]. O(log n)."""
if hi is None:
hi = self.n - 1
self.visited += 1
if right < lo or hi < left:
return 0
if left <= lo and hi <= right:
return self.total[node]
self._push(node, lo, hi)
mid = (lo + hi) // 2
return (self.query(left, right, 2 * node, lo, mid)
+ self.query(left, right, 2 * node + 1, mid + 1, hi))
lz = LazySumTree(a)
lz.add(0, 7, 5)
print("nodes touched by add on everything:", lz.visited)
print(lz.query(0, 7), "expected", sum(a) + 8 * 5)
lz.add(2, 5, -3)
print(lz.query(1, 4), "expected", 2 + 7 + 3 + 9 + 4 * 5 - 3 * 3)
# Output:
# nodes touched by add on everything: 1
# 77 expected 77
# 32 expected 32The second check needs a moment. Values 1 to 4 are 2, 7, 3, 9, and each got plus 5, which is plus 20. The second add of minus 3 touched positions 2 to 5, so positions 2, 3 and 4 inside the query lost 3 each. That is 21 + 20 - 9 = 32.
For other operations, such as setting a whole range to one value, deciding how a new tag combines with an old one is the hard part of the design. Mistakes there give wrong answers with no error, so test against a plain loop.
#Sqrt Decomposition: The Simple Middle Road
It then adds the totals of whole blocks in the middle, at most n divided by the block size. With block size near the square root of n, both parts are O(sqrt n).
import math
class SqrtBlocks:
"""Range sum by blocks of about sqrt(n) values. Update O(1), query O(sqrt n)."""
def __init__(self, values):
self.values = list(values)
self.size = max(1, math.isqrt(len(values)))
self.sums = [sum(self.values[i:i + self.size]) for i in range(0, len(values), self.size)]
self.steps = 0
def add(self, index, delta):
self.values[index] += delta
self.sums[index // self.size] += delta
self.steps += 1
def range_sum(self, left, right):
total = 0
while left <= right and left % self.size != 0: # loose values at the left end
total += self.values[left]
left += 1
self.steps += 1
while left + self.size - 1 <= right: # whole blocks in the middle
total += self.sums[left // self.size]
left += self.size
self.steps += 1
while left <= right: # loose values at the right end
total += self.values[left]
left += 1
self.steps += 1
return total
sq = SqrtBlocks(range(100))
print(sq.range_sum(3, 96), sum(range(3, 97)), "steps:", sq.steps)
# Output:
# 4653 4653 steps: 22The answer 4653 is right, and the 94-value range needed only 22 steps instead of 94: 7 loose values on the left, 8 whole blocks of 10, and 7 on the right.
Why bother when trees exist? The code is short and hard to get wrong. It works for any associative operation, including awkward ones such as "how many values in this block are above 50" that trees handle badly. The price is speed: for n = 100,000, sqrt n is about 316 while log2 n is about 17. Use it when the problem is odd and the numbers are modest.
#Which Structure? A Decision Table
Ask three questions in order. Does the data change? What operation is it, and is it invertible or idempotent? Do updates touch one value or a range?
| Situation | Use | Build | Query | Update | Space |
|---|---|---|---|---|---|
| Data never changes, sums | Prefix sums | O(n) | O(1) | rebuild, O(n) | O(n) |
| Data never changes, min, max or gcd | Sparse table | O(n log n) | O(1) | rebuild, O(n log n) | O(n log n) |
| Sums or xor, point updates | Fenwick tree | O(n) | O(log n) | O(log n) | O(n) |
| Min, max or any associative operation, point updates | Segment tree | O(n) | O(log n) | O(log n) | O(n) |
| Range updates with range queries | Lazy segment tree | O(n) | O(log n) | O(log n) | O(n) |
| Odd operation, small n, short code | Sqrt decomposition | O(n) | O(sqrt n) | O(1) | O(n) |
| Few queries, tiny n | Plain loop | none | O(n) | O(1) | O(1) |
Two further rules. If queries are few, the plain loop wins, because every structure costs build time and code. If an update changes a whole range and queries come rarely, a difference array (record the change at the two ends and add it up once at the end) is cheaper than any tree.
#Where This Shows Up
- Python builds prefix sums with
itertools.accumulate. The 2D version, called a summed-area table or integral image, gives the sum of any rectangle of pixels in four lookups. Classic face detectors in computer vision lean on it for this reason. - Databases keep summary information per block so a scan can skip blocks. For example, PostgreSQL's BRIN indexes and Parquet files store a minimum and a maximum for each block of rows. That is the sqrt decomposition idea with the cheapest possible block summary.
- A leaderboard can ask "what rank is this score?" by counting scores above it. A Fenwick tree over score values answers that and absorbs new scores in O(log n). The same count gives the number of inversions between two rankings, which is a standard way to measure how much they disagree.
- Many implementations of prioritized experience replay in reinforcement learning keep priorities in a sum tree, which is a segment tree over weights. It lets them draw a sample in proportion to its weight and change one weight, both in O(log n).
- The lowest common ancestor of two tree nodes can be turned into a range minimum on a walk around the tree. A sparse table then answers it in O(1) after O(n log n) preparation.
#Common Mistakes
#Try It: Five Problems
Work up the ladder. Each function counts its own work, so you can see the complexity in the printed numbers. Problem 1 is a warm-up. Problem 2 includes ranges whose length is exactly a power of two. Problem 3 asks for a Fenwick tree and the worst-case pass counts on 1,000 values. Problem 4 asks for a segment tree and a check that no query on 1,000 values visits more than 40 nodes. Problem 5 is adversarial: it counts inversions with a Fenwick tree on a list with duplicates, an empty list, and a list of 2,000 values in reverse order. A slow answer would take far too long on that last one.
Tests · Expected output, line by line. Line 1: 19 37 3 8. Line 2: ([0], 0). Line 3: (2, 2) (4, 2) (2, 2) (7, 2). Line 4: all 36 ranges match brute force: True. Line 5: 1000 512 1. Line 6: worst prefix steps: 9 add at the front: 10. Line 7: 1 1. Line 8: 3. Line 9: 42 1. Line 10: worst nodes visited: 39 limit: 40. Line 11: (3, 16). Line 12: (0, 6) (0, 0). Line 13: (1999000, 21990). Line 14: (0, 21990). The adversarial cases are the empty list, one value, all-equal values (zero inversions, because equal values do not count), and the reversed list of 2,000 values with the most inversions possible, 2000 times 1999 divided by 2. Lines 13 and 14 show the same step count, because the work depends on n, not on the order.
#Recap
A range query asks for a sum or a minimum over a stretch of an array. Three costs describe any answer: build, query and update. A plain loop has cheap updates and slow queries. Prefix sums have O(1) queries and O(n) updates, and only work for invertible operations.
A sparse table gives O(1) queries for idempotent operations like minimum, with O(n log n) build and space, and no updates. A Fenwick tree gives O(log n) sums and point updates in O(n) space, using lowbit to decide which stretch each cell holds. A segment tree gives O(log n) for any associative operation, because a query splits into at most four nodes per level.
Lazy propagation lets a segment tree update a whole range in O(log n) by leaving tags on whole nodes. Sqrt decomposition trades speed for simple code at O(sqrt n) per query. The decision table says which one fits.
A fixed array of 200,000 numbers gets 500,000 range-sum questions and no updates. Which choice is best?
Key Takeaways
- Three costs decide the choice: build, query and update, and a cheaper query usually buys a dearer update
- Prefix sums give O(1) queries but O(n) updates, and need an invertible operation
- A sparse table gives O(1) minimum queries in O(n log n) space, only for idempotent operations on data that never changes
- A Fenwick tree uses lowbit, i & -i, to give O(log n) updates and prefix queries in O(n) space for invertible operations
- A segment tree handles any associative operation in O(log n), because at most two nodes per level are partly inside a query
- Lazy tags make a range update O(log n), and sqrt decomposition trades speed for the simplest code at O(sqrt n)