DSA When Prefix Sums Fail
A prefix table stores the running total up to each index, so a range sum is one subtraction. When values change, the honest fixes are segment trees and Fenwick trees, with sqrt decomposition as the bridge.
The table answers fast
The prefix table stores one running total per index. Any range sum is then a single subtraction.
values = [4, 1, 7, 3, 9, 2]
prefix = [0]
for v in values:
prefix.append(prefix[-1] + v)
print("prefix:", prefix)
print("sum 1..3:", prefix[4] - prefix[1])
print("sum 0..5:", prefix[6] - prefix[0])One update breaks the table
Changing index 2 leaves the stored totals stale. The table answer disagrees with the true sum until the table is rebuilt.
values = [4, 1, 7, 3, 9, 2]
prefix = [0]
for v in values:
prefix.append(prefix[-1] + v)
values[2] = 10
print("true sum 1..3:", sum(values[1:4]))
print("table sum 1..3:", prefix[4] - prefix[1])
rewritten = 0
for i in range(len(values)):
prefix[i + 1] = prefix[i] + values[i]
rewritten += 1
print("cells rewritten:", rewritten)
print("fixed sum 1..3:", prefix[4] - prefix[1])Blocks with their own sums
Sqrt decomposition stores one sum per block of three. The query returns its sum and its step count, and a whole block costs one step.
values = [4, 1, 7, 3, 9, 2, 5, 8, 6]
size = 3
blocks = [sum(values[i:i + size]) for i in range(0, len(values), size)]
print("blocks:", [values[i:i + size] for i in range(0, len(values), size)])
print("block sums:", blocks)
def range_sum(left, right):
total = 0
steps = 0
i = left
while i <= right:
if i % size == 0 and i + size - 1 <= right:
total += blocks[i // size]
steps += 1
i += size
else:
total += values[i]
steps += 1
i += 1
return total, steps
print("sum 1..7:", range_sum(1, 7))
print("sum 0..8:", range_sum(0, 8))
values[4] = 20
blocks[1] += 20 - 9
print("block sums after update:", blocks)
print("sum 1..7 now:", range_sum(1, 7))Example
OPS = [("query", 0, 15), ("update", 4, 20), ("query", 2, 10),
("query", 0, 31), ("update", 20, 7), ("query", 8, 23),
("update", 0, 3), ("query", 5, 27), ("query", 0, 31),
("update", 15, 12), ("query", 3, 18), ("query", 0, 31)]
BASE = [(i * 7) % 13 + 1 for i in range(32)]
def run_plain():
values = list(BASE)
cost = len(values)
answers = []
for op in OPS:
if op[0] == "update":
values[op[1]] = op[2]
cost += 1
else:
total = 0
for i in range(op[1], op[2] + 1):
total += values[i]
cost += 1
answers.append(total)
return cost, answers
def run_prefix():
values = list(BASE)
prefix = [0]
cost = 0
for v in values:
prefix.append(prefix[-1] + v)
cost += 1
answers = []
for op in OPS:
if op[0] == "update":
values[op[1]] = op[2]
for i in range(len(values)):
prefix[i + 1] = prefix[i] + values[i]
cost += 1
else:
answers.append(prefix[op[2] + 1] - prefix[op[1]])
cost += 1
return cost, answers
def run_sqrt():
size = 6
values = list(BASE)
blocks = []
cost = 0
for i in range(0, len(values), size):
blocks.append(sum(values[i:i + size]))
cost += min(size, len(values) - i)
answers = []
for op in OPS:
if op[0] == "update":
blocks[op[1] // size] += op[2] - values[op[1]]
values[op[1]] = op[2]
cost += 2
else:
total = 0
i = op[1]
while i <= op[2]:
if i % size == 0 and i + size - 1 <= op[2]:
total += blocks[i // size]
cost += 1
i += size
else:
total += values[i]
cost += 1
i += 1
answers.append(total)
return cost, answers
plain_cost, plain_answers = run_plain()
prefix_cost, prefix_answers = run_prefix()
sqrt_cost, sqrt_answers = run_sqrt()
print("answers agree:", plain_answers == prefix_answers == sqrt_answers)
print("answers:", plain_answers)
print("plain list cost:", plain_cost)
print("prefix table cost:", prefix_cost)
print("sqrt blocks cost:", sqrt_cost)Key points
- A range sum reads two stored totals and subtracts them once
- An update changes one value but invalidates every later total
- Rebuilding the table after an update rewrites all n of its cells
- A plain list updates in one step and rescans the whole range per query
- Sqrt decomposition groups the list into blocks with one stored sum per block
- A sqrt query adds whole block sums and scans only the partial edge blocks
- A sqrt update adjusts one block sum by the change in its element
In this example, one scripted workload of four updates and eight queries runs on 32 values three ways. The plain list pays 212 steps because every query rescans its range. The prefix table pays 168 steps because each update rewrites all 32 cells. The sqrt version pays 96 steps, since queries read whole block sums and updates touch one block. The next two lessons build the segment tree and the Fenwick tree, which cut both operations to log n steps.
Try it Yourself
Edit the code, then press Run.
Running is simulated · Python Playground
Exercise
One value in a list changes. How many entries of its prefix table can be stale afterwards?