DSA Prefix Sum

A prefix sum is a list of running totals. Each entry holds the sum of all items from the start up to that position. Building the list once lets you answer "what is the total between position A and position B?" in a single step.

Imagine the odometer in a car. It shows the total distance traveled since the car was new. To find how far you drove between two gas stops, you subtract the first reading from the second. You never add up every small trip. Prefix sums apply the same trick to lists.

The Problem It Solves

A shop keeps daily sales in a list. The owner asks for the total sales from day 2 to day 5, from day 1 to day 4, and for many other ranges. Adding the numbers fresh for every question wastes time. A prefix sum list removes that repeated work.

Building the Prefix List

def build_prefix(numbers):
    prefix = [0]
    for n in numbers:
        prefix.append(prefix[-1] + n)
    return prefix

sales = [3, 1, 4, 1, 5, 9]
prefix = build_prefix(sales)
print(prefix)   # [0, 3, 4, 8, 9, 14, 23]

Sales:   3   1   4   1   5   9
Prefix: 0   3   4   8   9  14  23
        ^   ^   ^   ^   ^   ^   ^
       none d1  d1-2 d1-3 d1-4 d1-5 d1-6

The extra 0 at the front keeps the range formula clean for ranges that start at the first item.

Range Sum Formula

The sum of items from index left to index right equals prefix[right + 1] minus prefix[left].

def range_sum(prefix, left, right):
    return prefix[right + 1] - prefix[left]

print(range_sum(prefix, 1, 3))   # 6  (1 + 4 + 1)

Range index 1 to 3  = [1, 4, 1]

prefix[4] = 9   (everything up to index 3)
prefix[1] = 3   (everything before index 1)

9 - 3 = 6

Building the list costs O(n) once. Every range question after that costs O(1).

Example: Count Subarrays With Sum k

A harder question asks how many continuous sections of a list add up to a target number k. A dictionary tracks how often each running total has appeared.

def count_subarrays(numbers, k):
    count = 0
    running = 0
    seen = {0: 1}
    for n in numbers:
        running += n
        count += seen.get(running - k, 0)
        seen[running] = seen.get(running, 0) + 1
    return count

print(count_subarrays([1, 2, 3], 3))   # 2

The sections [1, 2] and [3] both add up to 3. When the running total minus k equals an earlier running total, the items between those two points sum to k.

Example: Find the Balance Point

An equilibrium index splits a list so the left side and right side have equal sums.

def balance_point(numbers):
    total = sum(numbers)
    left = 0
    for i, n in enumerate(numbers):
        if left == total - left - n:
            return i
        left += n
    return -1

print(balance_point([1, 7, 3, 6, 5, 6]))   # 3

At index 3, the left side adds to 1 + 7 + 3 = 11 and the right side adds to 5 + 6 = 11. The loop tracks the left total as it moves and gets the right total by subtraction, so it never re-adds the list.

Real-Life Uses

Fitness apps report total steps between two dates. Banking tools show the balance change across a date range. Image editors compute the brightness of a rectangular region quickly using a two-dimensional version of the idea. Analytics dashboards answer range questions on millions of records without delay.

Practice Ideas

Try building a prefix list for your own weekly expenses and answer three range questions by hand. Compare each answer with the formula. Extend the idea by storing prefix counts of vowels in a sentence, which lets you count vowels in any word range instantly.

Common Mistakes

Off-by-one errors top the list. Forgetting the leading 0 shifts every answer by one position. Mixing inclusive and exclusive ends confuses the formula. Write a tiny example by hand and compare it with the program output before trusting the code.

Complexity Summary

• Build time: O(n)
• Each range query: O(1)
• Space: O(n) for the prefix list

Key Points

• A prefix sum stores running totals of a list.
• Range sum equals prefix[right + 1] minus prefix[left].
• One build pass makes every later query instant.
• A dictionary of running totals counts subarrays with a target sum.
• The leading 0 keeps the formula simple.