Prefix Sum

Before we start

By the end of this page you will be able to:

• See prefix sums as a precomputed cheat sheet, not just an array.
• Explain out loud why range_sum(l, r) = prefix[r] - prefix[l-1] is always correct.
• Recognise when a problem is secretly a prefix-sum problem and apply the pattern immediately.

When you hit a Pause & Think box, stop reading and think. That five-second investment is what burns it in.

Picture this first (no code yet)

Jan  Feb  Mar  Apr  May  Jun  Jul  Aug  Sep  Oct  Nov  Dec
₹200 ₹150 ₹300 ₹250 ₹180 ₹220 ₹190 ₹210 ₹240 ₹260 ₹170 ₹300

End of Jan: 200
End of Feb: 200 + 150 = 350
End of Mar: 350 + 300 = 650
End of Apr: 650 + 250 = 900
End of May: 900 + 180 = 1080
End of Jun: 1080 + 220 = 1300
End of Jul: 1300 + 190 = 1490
End of Aug: 1490 + 210 = 1700
...

That running total is called a prefix sum array. It is the single most useful precomputation trick in competitive programming and interviews.

The actual problem

Here is the coding version:

Given an array of integers, answer multiple queries of the form "what is the sum of elements from index l to index r (inclusive)?"

array   = [3, 1, 4, 1, 5, 9, 2, 6]
query 1 : sum from index 2 to 5  →  4 + 1 + 5 + 9  =  19
query 2 : sum from index 0 to 3  →  3 + 1 + 4 + 1  =  9
query 3 : sum from index 5 to 7  →  9 + 2 + 6       =  17

With one preprocessing pass, you answer each query in O(1).

First, the slow way (so you feel the pain)

The obvious approach: loop from l to r and add up every element.

def range_sum_slow(arr, l, r):
    total = 0
    for i in range(l, r + 1):
        total += arr[i]
    return total

For a single query this is fine — O(r − l + 1) work. But what happens with many queries?

n = 100,000 elements
Q = 100,000 queries, each spanning the whole array

Slow: 100,000 × 100,000 = 10,000,000,000 operations  (ten billion — hours of runtime)

Even with modest inputs, repeated range queries become a bottleneck in real systems. We need something better.

The turning point

Exactly: sum(l, r) = total(r) − total(l − 1).

The total through r includes everything from 0 to r. The total through l-1 includes everything from 0 to l-1. Their difference is exactly what's between l and r. The overlapping left portion cancels out.

Now the only question is: can we make total(i) answer in O(1)? Yes — precompute it for every index and store it in an array. That's the prefix sum.

The one idea to remember

Build it once in O(n). Answer every query in O(1) forever after.

Watch it happen, frame by frame

Array: [3, 1, 4, 1, 5, 9, 2, 6] (zero-indexed, length 8).

Building the prefix sum array:

We define prefix[i] = sum of arr[0] through arr[i].

i=0:  prefix[0] = arr[0]                  = 3
i=1:  prefix[1] = prefix[0] + arr[1]      = 3  + 1  = 4
i=2:  prefix[2] = prefix[1] + arr[2]      = 4  + 4  = 8
i=3:  prefix[3] = prefix[2] + arr[3]      = 8  + 1  = 9
i=4:  prefix[4] = prefix[3] + arr[4]      = 9  + 5  = 14
i=5:  prefix[5] = prefix[4] + arr[5]      = 14 + 9  = 23
i=6:  prefix[6] = prefix[5] + arr[6]      = 23 + 2  = 25
i=7:  prefix[7] = prefix[6] + arr[7]      = 25 + 6  = 31

prefix = [3, 4, 8, 9, 14, 23, 25, 31]

Answering queries:

Query: sum(2, 5)  →  prefix[5] − prefix[1]  =  23 − 4  =  19  ✅
Query: sum(0, 3)  →  prefix[3] − prefix[-1]
                     (l=0, so no left part; answer = prefix[3] = 9)  ✅
Query: sum(5, 7)  →  prefix[7] − prefix[4]  =  31 − 14 =  17  ✅

Now, the code — line by line

def build_prefix(arr):
    n = len(arr)
    prefix = [0] * n            # same length as arr

    prefix[0] = arr[0]          # the first running total is just the first element

    for i in range(1, n):
        prefix[i] = prefix[i-1] + arr[i]   # each entry = previous total + current element

    return prefix


def range_sum(prefix, l, r):
    if l == 0:
        return prefix[r]                     # no left portion to subtract
    return prefix[r] - prefix[l - 1]        # total through r  minus  total through l-1

Mapping each line to the phone bill:

• prefix[0] = arr[0] — "Running total at the end of January = January's bill."
• prefix[i] = prefix[i-1] + arr[i] — "Running total this month = last month's total + this month's charge."
• prefix[r] - prefix[l-1] — "Spending from month l to month r = total through r minus total through l-1."
• if l == 0: return prefix[r] — "If l=0, there's no previous total to subtract — the answer is just prefix[r] itself."

A cleaner version with a sentinel zero

Many implementations shift the prefix array by one and prepend a zero. This eliminates the if l == 0 edge case:

def build_prefix_v2(arr):
    n = len(arr)
    prefix = [0] * (n + 1)          # length n+1; prefix[0] = 0 (sentinel)

    for i in range(n):
        prefix[i + 1] = prefix[i] + arr[i]

    return prefix


def range_sum_v2(prefix, l, r):
    return prefix[r + 1] - prefix[l]   # no special case needed

prefix[i] now means "sum of the first i elements." range_sum(l, r) = prefix[r+1] - prefix[l] always works, even when l = 0.

Which to use? The sentinel-zero version is cleaner. Learn to recognise both — you'll see both in real code.

Why does the formula always work?

prefix[r]   = arr[0] + arr[1] + … + arr[l-1] + arr[l] + … + arr[r]
prefix[l-1] = arr[0] + arr[1] + … + arr[l-1]

prefix[r] - prefix[l-1]
= (arr[0] + … + arr[l-1] + arr[l] + … + arr[r])
  −
  (arr[0] + … + arr[l-1])
= arr[l] + arr[l+1] + … + arr[r]    ✅

The left chunk arr[0..l-1] appears in both terms and cancels out exactly. What remains is the slice you asked for.

Why is it so fast?

Compare to the naive approach:

Naive  (n=100,000, Q=100,000):  ~10,000,000,000 operations
Prefix (n=100,000, Q=100,000):  ~200,000 operations

A fifty-thousand times speedup for heavy query workloads.

When should I reach for this? (the trigger list)

Reach for prefix sum when you notice:

• The problem asks for sums (or counts) over a range of an array repeatedly.
• You see the phrase "subarray sum", "range query", or "from index l to r."
• The brute-force solution loops inside a loop — O(n) per query → O(n²) total.
• The array is static (doesn't change between queries). If it changes, you need a different structure (segment tree / Fenwick tree — much later chapters).
• You're asked to count subarrays satisfying a condition — this often reduces to prefix sums + a hash map (see below).

The same trick in five disguises

Disguise 1 — Range Sum Query (LC #303)

The textbook application. Build prefix once, __init__. Answer every sumRange(l, r) in O(1).

class NumArray:
    def __init__(self, nums):
        n = len(nums)
        self.prefix = [0] * (n + 1)
        for i in range(n):
            self.prefix[i + 1] = self.prefix[i] + nums[i]

    def sumRange(self, left, right):
        return self.prefix[right + 1] - self.prefix[left]

Disguise 2 — Subarray Sum Equals K (LC #560)

Count subarrays whose elements sum to exactly k. The key reframing: a subarray arr[l..r] has sum k when prefix[r] − prefix[l−1] = k, i.e. prefix[l−1] = prefix[r] − k.

So: for each r, ask "how many times have I already seen the prefix sum value prefix[r] − k?" — answer with a hash map.

def subarraySum(nums, k):
    count = 0
    running = 0
    seen = {0: 1}          # prefix sum 0 seen once before we start

    for x in nums:
        running += x
        need = running - k
        count += seen.get(need, 0)    # how many earlier prefixes equal running - k?
        seen[running] = seen.get(running, 0) + 1

    return count

Why {0: 1}? A subarray starting from index 0 has prefix[l-1] = prefix[-1] = 0. Preloading 0 ensures we count those correctly.

This is one of the most important variations — it transforms a naive O(n²) problem into O(n) with a single hash map.

Disguise 3 — Find Pivot Index (LC #724)

"Find index i where left_sum = right_sum." That's just prefix[i-1] == total - prefix[i].

def pivotIndex(nums):
    total = sum(nums)
    left = 0
    for i, x in enumerate(nums):
        if left == total - left - x:   # left_sum == right_sum
            return i
        left += x
    return -1

The "prefix" here is tracked as a running variable — same idea, no extra array needed when you only need the current running total.

Disguise 4 — Product of Array Except Self (LC #238)

The upcoming chapter covers this as Suffix Product, but it's worth previewing: compute a prefix product (all elements to the left of i) and a suffix product (all elements to the right). Multiply them for the answer at each position. Two passes, O(n) space — no division needed.

Disguise 5 — 2D Prefix Sum (LC #304)

For a matrix, extend the idea: prefix[r][c] = sum of the rectangle from (0,0) to (r,c). Querying any rectangle uses four corner values. Same one-subtraction idea extended to two dimensions.

# Build
for r in range(rows):
    for c in range(cols):
        prefix[r+1][c+1] = (matrix[r][c]
                             + prefix[r][c+1]
                             + prefix[r+1][c]
                             - prefix[r][c])   # subtract the overlap counted twice

# Query rectangle (r1,c1) to (r2,c2)
def sumRegion(r1, c1, r2, c2):
    return (prefix[r2+1][c2+1]
            - prefix[r1][c2+1]
            - prefix[r2+1][c1]
            + prefix[r1][c1])

Traps that catch beginners

Say it like a pro (interview one-liner)

"I'll precompute a prefix sum array in O(n) so that any range sum query is just a single subtraction — O(1) per query. For counting subarrays that sum to k, I use prefix sums with a hash map: for each index, I check how many earlier prefix values equal current_prefix − k. That gets me O(n) time overall."

Check yourself

Practice problems

Next up: Suffix Sum — Product of Array Except Self, where we precompute from the right end and combine it with a prefix product to answer a tricky problem with no division and no extra space.