Prefix Sums

A prefix sum (also called a cumulative sum) is a precomputed array where each position holds the running total of all elements up to that index in the original array. Once built, it lets you answer "what is the sum of elements from index left to index right?" in constant time, no matter how wide the range is. This turns a repeated O(n) computation into a one-time O(n) setup followed by O(1) queries, which is why prefix sums show up constantly in array and string problems, especially ones involving many range queries or counting subarrays that satisfy a sum condition.

Overview: How Prefix Sums Work

Imagine a teacher recorded daily attendance counts for a semester and now needs to answer many questions like "how many students attended in total between day 10 and day 40?" Re-adding the numbers in that range every single time a question arrives is wasteful: with q questions over n numbers, naive re-summing costs O(q · n) in the worst case. A prefix sum array fixes this by doing the addition once, up front, then answering every future query with a single subtraction.

The standard construction uses an array of length n + 1 with a leading zero. Define prefix[0] = 0, and for every index i from 0 to n - 1, set prefix[i + 1] = prefix[i] + nums[i]. After this loop, prefix[i] holds the sum of the first i elements of nums (that is, nums[0] through nums[i - 1]). The leading zero is not a stylistic choice — it is what lets you query a range starting at index 0 without a special case, because subtracting prefix[0] = 0 removes nothing.

To get the sum of a range [left, right] inclusive, compute prefix[right + 1] - prefix[left]. Why does this work? prefix[right + 1] is the sum of everything from index 0 through right. prefix[left] is the sum of everything from index 0 through left - 1 — exactly the part that comes before the range you want. Subtracting it cancels out that shared prefix, leaving only the sum of nums[left..right]. This is the same idea as reading a car’s odometer at the start and end of a trip: the distance traveled is end_reading - start_reading, not a fresh recount of every mile.

Prefix sums become even more powerful when paired with a hash map. A huge class of problems asks "how many subarrays sum to exactly k?" instead of "what is the sum of one specific range?" The key identity is: a subarray ending at index j and starting right after index i sums to k exactly when prefix[j] - prefix[i] = k, which rearranges to prefix[i] = prefix[j] - k. So as you scan left to right building the running prefix sum, at each position you ask a hash map "how many earlier prefix sums equal current_sum - k?" and add that count to your answer. This turns an O(n²) brute-force search over all subarrays into a single O(n) pass.

A related but distinct technique is the difference array, which is the inverse operation: instead of answering range-sum queries on a static array, it applies many range updates (add a value to every element in [left, right]) efficiently, then reconstructs the final array with one prefix-sum pass at the end. If your problem repeatedly mutates a range rather than querying it, look for "difference array" or "range update, single query at the end" patterns.

Time and Space Complexity

The complexity of prefix sums splits cleanly into a one-time build cost and a cheap per-query cost. The table below assumes an input of size n.

Operation	Time	Space	Why
Build the prefix sum array	O(n)	O(n)	One linear pass adds each element once; the output array stores n + 1 running totals.
Range sum query (after build)	O(1)	O(1)	Just one array lookup and one subtraction, regardless of range width.
Answering q range queries total	O(n + q)	O(n)	O(n) once to build, then O(1) per query instead of O(n) per query.
Update one element, then query again	O(n) to rebuild	O(n)	Changing one value shifts every prefix sum after it, so a full rebuild is the safe correct approach with a plain array.
Subarray-sum-equals-k (prefix sum + hash map)	O(n) average	O(n)	One pass; each hash map lookup and insert is O(1) average. Worst case O(n) per operation only under pathological hash collisions, which Python’s dict resists well in practice.

The key trade-off to remember: prefix sums shine when the array is mostly static and you need many range-sum queries. If the array is updated frequently and you still need fast range queries after every update, a plain prefix sum array is the wrong tool — a Binary Indexed Tree (Fenwick tree) or Segment Tree gives O(log n) updates and O(log n) queries instead of O(n) rebuilds.

Examples

Example 1: Range sum queries in O(1)

def build_prefix_sums(nums: list[int]) -> list[int]:
    prefix = [0] * (len(nums) + 1)
    for i, num in enumerate(nums):
        prefix[i + 1] = prefix[i] + num
    return prefix


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


nums = [4, 2, -1, 3, 5, 1]
prefix = build_prefix_sums(nums)
print(prefix)
print(range_sum(prefix, 1, 3))
print(range_sum(prefix, 0, 5))

Output:

[0, 4, 6, 5, 8, 13, 14]
4
14

Tracing it: build_prefix_sums walks nums = [4, 2, -1, 3, 5, 1] and accumulates prefix = [0, 4, 6, 5, 8, 13, 14]. The query range_sum(prefix, 1, 3) asks for nums[1] + nums[2] + nums[3] = 2 + (-1) + 3 = 4, computed as prefix[4] - prefix[1] = 8 - 4 = 4. The query range_sum(prefix, 0, 5) asks for the sum of the whole array, computed as prefix[6] - prefix[0] = 14 - 0 = 14, matching 4 + 2 - 1 + 3 + 5 + 1 = 14.

Example 2: Counting subarrays that sum to k

from collections import defaultdict


def subarray_sum_equals_k(nums: list[int], k: int) -> int:
    prefix_sum_counts = defaultdict(int)
    prefix_sum_counts[0] = 1
    running_sum = 0
    count = 0
    for num in nums:
        running_sum += num
        count += prefix_sum_counts[running_sum - k]
        prefix_sum_counts[running_sum] += 1
    return count


nums = [1, 2, 3, -3, 4, 1]
k = 3
print(subarray_sum_equals_k(nums, k))

Output:

3

Here prefix_sum_counts starts with {0: 1} to represent the empty prefix. As the running sum becomes 1, 3, 6, 3, 7, 8, the code checks, at each step, how many earlier prefix sums equal running_sum - k. This finds three subarrays summing to 3: [1, 2], [1, 2, 3, -3], and [3] (the single element at index 2). Note that a subarray sum can repeat (running sum hits 3 twice), which is exactly why a hash map count is needed rather than a hash set.

Example 3: Finding a pivot index (realistic use)

def pivot_index(nums: list[int]) -> int:
    total = sum(nums)
    left_sum = 0
    for i, num in enumerate(nums):
        right_sum = total - left_sum - num
        if left_sum == right_sum:
            return i
        left_sum += num
    return -1


nums = [1, 7, 3, 6, 5, 6]
print(pivot_index(nums))

Output:

3

This is a compact variant of the prefix sum idea: instead of materializing a full prefix array, it tracks left_sum as a running total and derives right_sum from the overall total. With nums = [1, 7, 3, 6, 5, 6], total = 28. At i = 3 (value 6), left_sum has accumulated 1 + 7 + 3 = 11, and right_sum = 28 - 11 - 6 = 11, so left and right sums match and index 3 is returned as the pivot.

How It Works, Step by Step

Take nums = [3, 1, 4, 1, 5] and suppose we want the sum of the range [1, 3] (values at indices 1, 2, and 3). Building the prefix array:

• prefix[0] = 0 (the empty prefix, before any elements)
• prefix[1] = prefix[0] + nums[0] = 0 + 3 = 3
• prefix[2] = prefix[1] + nums[1] = 3 + 1 = 4
• prefix[3] = prefix[2] + nums[2] = 4 + 4 = 8
• prefix[4] = prefix[3] + nums[3] = 8 + 1 = 9
• prefix[5] = prefix[4] + nums[4] = 9 + 5 = 14

The finished array is [0, 3, 4, 8, 9, 14]. To answer the query for range [1, 3], compute prefix[right + 1] - prefix[left] = prefix[4] - prefix[1] = 9 - 3 = 6. Checking by hand: nums[1] + nums[2] + nums[3] = 1 + 4 + 1 = 6. The subtraction removed exactly the part of the running total that came before index 1 (namely, just nums[0] = 3), leaving the sum of indices 1 through 3 untouched.

Common Mistakes

Mistake 1: Off-by-one indexing (forgetting the leading zero)

A very common bug is building a prefix array the same length as nums (no leading zero) and then subtracting prefix[left] directly, which accidentally excludes nums[left] from the result:

def range_sum_wrong(nums: list[int], left: int, right: int) -> int:
    prefix = [0] * len(nums)
    prefix[0] = nums[0]
    for i in range(1, len(nums)):
        prefix[i] = prefix[i - 1] + nums[i]
    return prefix[right] - prefix[left]


nums = [4, 2, -1, 3, 5, 1]
print(range_sum_wrong(nums, 1, 3))

Output:

2

Here prefix[i] now means "sum through index i inclusive," so prefix[left] already includes nums[left]. Subtracting it removes that element too, so range_sum_wrong(nums, 1, 3) returns 2 (the sum of just indices 2 and 3) instead of the correct 4 (indices 1 through 3). The fix is the pattern from Example 1: use a prefix array of length n + 1 with a leading zero, and query with prefix[right + 1] - prefix[left], so prefix[left] represents everything strictly before left.

Mistake 2: Forgetting the base case in the hash-map pattern

When counting subarrays that sum to k, it’s tempting to start the hash map empty. But then any subarray starting at index 0 whose running sum equals k exactly gets silently missed, because there’s no earlier prefix sum of 0 to match against:

def subarray_sum_equals_k_wrong(nums: list[int], k: int) -> int:
    prefix_sum_counts = {}
    running_sum = 0
    count = 0
    for num in nums:
        running_sum += num
        if running_sum - k in prefix_sum_counts:
            count += prefix_sum_counts[running_sum - k]
        if running_sum in prefix_sum_counts:
            prefix_sum_counts[running_sum] += 1
        else:
            prefix_sum_counts[running_sum] = 1
    return count


nums = [3, 4, 7]
k = 7
print(subarray_sum_equals_k_wrong(nums, k))

Output:

1

The correct answer is 2: both [3, 4] and [7] sum to 7. The buggy version only finds [7], because it never registers that a running sum of 0 (the state before any elements) occurred once. The fix, shown in Example 2, is to seed the map with prefix_sum_counts[0] = 1 before the loop starts, representing the empty prefix.

Best Practices

• Reach for a prefix sum array when you have a static or rarely-changing array and need to answer many range-sum queries — it converts O(n) per query into O(1) per query.
• Use the n + 1-length array with a leading zero (prefix[0] = 0) so you never need a special case for a range starting at index 0.
• When the problem asks "how many subarrays satisfy some sum condition" rather than "what is the sum of one range," combine prefix sums with a hash map (dict or collections.defaultdict) and remember to seed it with the empty-prefix base case.
• If the array is updated frequently and you still need fast range queries afterward, don’t use a plain prefix sum array (O(n) rebuild per update) — use a Fenwick tree (Binary Indexed Tree) or Segment Tree for O(log n) updates and queries instead.
• For problems that apply many range updates and only need the final array once, use a difference array (prefix sums in reverse) instead of updating every element in each range directly.
• Python integers have arbitrary precision, so there’s no overflow risk in running sums — unlike fixed-width-integer languages, you never need to worry about a prefix sum exceeding a max value.

Practice Exercises

1. Range Sum Query — Immutable. Implement a class NumArray with a constructor that takes a list of integers and a method sum_range(left: int, right: int) -> int that returns the sum of the elements between the two indices, inclusive, answered in O(1) per call after O(n) preprocessing. Hint: store the prefix sum array as an instance attribute in the constructor.
2. Maximum length of a balanced binary subarray. Given an array containing only 0s and 1s, find the length of the longest contiguous subarray with an equal number of 0s and 1s. Hint: treat every 0 as -1, take a running sum, and use a hash map that stores the first index at which each running sum value was seen — the distance between two indices with the same running sum is a balanced subarray.
3. Count subarrays with sum divisible by k. Given an integer array and an integer k, count how many contiguous subarrays have a sum divisible by k. Hint: two prefix sums with the same remainder modulo k mark the ends of a subarray whose sum is divisible by k; in Python, use running_sum % k as the hash map key (Python’s % always returns a non-negative result for a positive k, which keeps the keys consistent even with negative numbers in the array).

Summary

• A prefix sum array stores running totals so that the sum of any range can be computed with one subtraction instead of re-adding elements.
• Build with a leading zero, length n + 1: prefix[i + 1] = prefix[i] + nums[i]. Query a range [left, right] with prefix[right + 1] - prefix[left].
• Building costs O(n) time and O(n) space; each query afterward costs O(1) time and O(1) extra space.
• Combine prefix sums with a hash map to count subarrays matching a sum condition in O(n) average time, using the identity prefix[i] = prefix[j] - k.
• Always seed the hash map with the empty-prefix base case ({0: 1}) or you will undercount subarrays that start at index 0.
• Use the n + 1-length convention to avoid off-by-one errors when the range starts at index 0.
• Prefix sums are ideal for static arrays with many queries; for arrays with frequent updates, prefer a Fenwick tree or Segment Tree, and for many range updates, prefer a difference array.