Prefix Sums and Range Queries
22 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)A report asks for the total sales between two days, and the dates change all day. Adding the same days again for every request wastes time. A prefix sum does the adding once, so each question after that takes one subtraction.
Adding a slice every time
Range query is a question about the items between two positions of a list, such as their sum. Prefix sums answer many range queries on the same list quickly.
A shop keeps daily sales in a list. A report asks for the total from day 2 to day 5, again and again. The direct way adds that slice for every request.
sales = [120, 80, 150, 60, 200, 90, 110]
def range_sum_slow(low, high): return sum(sales[low:high + 1])
print(range_sum_slow(2, 5))Example 1 · Brute force, many queries
sales = [120, 80, 150, 60, 200, 90, 110]queries = [(0, 2), (2, 5), (4, 6)]for low, high in queries: print(low, high, sum(sales[low:high + 1]))0 2 350 2 5 500 4 6 400
What this code does
- Every query builds a slice and adds it up again.
- With three queries this is fine. With a million queries on a long list it is too slow.
This is the brute force. One query costs time equal to the length of the range, so q queries on n days can cost O(n * q).
Build the running totals once
Prefix sum is the total of the first i items of a list. A prefix sum list stores that total for every i, so prefix[0] is 0 and prefix[n] is the sum of the whole list.
Keep a running total. Let prefix[i] hold the sum of the first i items, so prefix[0] is 0. One pass over the list builds all of it.
sales = [120, 80, 150, 60, 200, 90, 110]
prefix = [0]for amount in sales: prefix.append(prefix[-1] + amount)
print(prefix)Example 2 · The prefix list, step by step
sales = [4, 2, 7]prefix = [0]for amount in sales: prefix.append(prefix[-1] + amount) print(amount, prefix)4 [0, 4] 2 [0, 4, 6] 7 [0, 4, 6, 13]
What this code does
prefix[-1]is the last running total.- Each new value is the old total plus the new amount, so the work per item is constant.
The list has n + 1 values. Building it costs O(n) time and O(n) extra space, and you do it only once.
Any range with one subtraction
The sum of days low to high is everything up to high minus everything before low. That is prefix[high + 1] - prefix[low], whatever the length of the range.
sales = [120, 80, 150, 60, 200, 90, 110]prefix = [0, 120, 200, 350, 410, 610, 700, 810]
def range_sum(low, high): return prefix[high + 1] - prefix[low]
print(range_sum(2, 5))print(range_sum(0, 6))print(range_sum(3, 3))Example 3 · Many queries, one subtraction each
sales = [120, 80, 150, 60, 200, 90, 110]prefix = [0]for amount in sales: prefix.append(prefix[-1] + amount)
for low, high in [(0, 2), (2, 5), (4, 6), (3, 3)]: print(low, high, prefix[high + 1] - prefix[low])0 2 350 2 5 500 4 6 400 3 3 60
What this code does
- The same answers as the brute force, but no slice and no loop per query.
- A single day, such as (3, 3), also works: prefix[4] - prefix[3] is the item at index 3.
Each query is now O(1). Building costs O(n) once, then q queries cost O(q), so the total is O(n + q).
accumulate builds it in one line
itertools.accumulate is a function that produces the running total of an iterable, one value per item. initial=0 adds a starting 0, and a second argument such as max changes the operation.
The standard library already has the running total. Pass initial=0 to put the leading 0 in front, then wrap the result in list.
from itertools import accumulate
sales = [120, 80, 150, 60, 200, 90, 110]prefix = list(accumulate(sales, initial=0))print(prefix)print(prefix[6] - prefix[2])Example 4 · accumulate with different operations
from itertools import accumulate
marks = [40, 72, 65, 90, 85]print(list(accumulate(marks)))print(list(accumulate(marks, initial=0)))print(list(accumulate(marks, max)))[40, 112, 177, 267, 352] [0, 40, 112, 177, 267, 352] [40, 72, 72, 90, 90]
What this code does
- The first line is the running sum. The second starts with 0, which is what range queries need.
- A function as the second argument replaces addition. With
maxyou get the best mark so far.
Example 5 · Running balance of an account
from itertools import accumulate
changes = [500, -200, -400, 300]balance = list(accumulate(changes))print(balance)day = next((i for i, b in enumerate(balance) if b < 0), None)print(day)[500, 300, -100, 200] 2
What this code does
- accumulate turns daily changes into the balance after each day. Negative numbers work the same way.
next(..., None)returns the first day the balance is below zero, or None when it never is.
Example 6 · Equilibrium index without a list
def pivot(items): total = sum(items) left = 0 for i, x in enumerate(items): if left == total - left - x: return i left += x return -1
print(pivot([2, 4, 9, 3, 3]))print(pivot([1, 2, 3]))2 -1
What this code does
leftis a prefix sum kept as one number. The right side is the total minus left minus the current item.- It finds the first index where both sides are equal, using O(n) time and O(1) extra space.
In an interview, also be ready to write the loop by hand. Both give the same list.
Next step
Check your understanding
12 quick questions