🎓 A1Learner
🔍

DSA Prefix Sums

A prefix sum is the running total of a list up to each position. One prefix table answers the sum of any stretch with one subtraction.

Building the prefix table

Each entry adds one more value to the total so far. The table opens with zero, the total before any value.

values = [2, 4, 6]
prefix = [0]
for value in values:
    prefix.append(prefix[-1] + value)
print(prefix)

A range sum by subtraction

A range sum is the total of a run of neighbouring values. The run from index 1 to index 2 is one prefix minus an earlier prefix.

prefix = [0, 2, 6, 12]
print(prefix[3] - prefix[1])
print(4 + 6)

One build, many queries

Each query names a start and an end index. The same subtraction answers every query.

prefix = [0, 2, 6, 12]
queries = [(0, 2), (1, 1), (2, 2)]
for start, end in queries:
    print(prefix[end + 1] - prefix[start])

Example

values = [3, 1, 4, 1, 5, 9, 2, 6]
prefix = [0]
for value in values:
    prefix.append(prefix[-1] + value)
print("values:", values)
print("prefix:", prefix)
subtractions = 0
queries = [(0, 3), (2, 5), (4, 7), (1, 6)]
for start, end in queries:
    total = prefix[end + 1] - prefix[start]
    subtractions += 1
    print("sum", start, "to", end, "=", total)
print("subtractions:", subtractions)

Key points

  • Prefix sum: the running total of a list up to a position
  • The sum from start to end is prefix[end + 1] minus prefix[start]
  • Building the table takes one pass over the values
  • Each range query then costs one subtraction

In this example, one pass builds the prefix table for eight values. Each query then subtracts the prefix before its start from the prefix after its end. Four queries cost four subtractions in total. Building the table once pays for every later query.

Note

The table holds one more entry than the list, because of the opening zero

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

What is the prefix table for the list [5, 5, 5]?