Prefix Sums Explained Visually: O(1) Range Queries

Prefix sums are the cheapest idea in this whole subject and one of the most reused. Ten lines, no clever data structure, and the payoff is that a question you were going to answer in O(n) per query becomes a single subtraction.

The problem it solves

You are asked for the sum of a range: elements 3 through 7, then 0 through 4, then 2 through 9. Each answer on its own is a loop, and the loop is O(n). Run q of them and you have O(n·q) — fine for one query, hopeless for a hundred thousand.

The observation that fixes it is almost too simple to notice. The sum of a range is the difference of two totals measured from the same starting point. If you know how much the array has accumulated before index i, and how much it has accumulated through index j, you know what lies between them without touching a single element in the middle.

The intuition

Think of a trip odometer rather than a speedometer. The array is what happened at each step; the prefix array is the running total after each step. To find the distance covered between two towns you read two odometer values and subtract — you do not re-drive the road.

prefix[k] is the sum of everything strictly before index k. Then the sum of nums[i..j] is prefix[j + 1] - prefix[i].

The two details that make this usable in an interview are both about the off-by-one:

1. The prefix array is one longer than the input. It has n+1 entries, because there are n+1 boundaries between and around n elements.
2. It starts with a 0. That entry is the sum of nothing — the state before the array begins. Without it, any range that starts at index 0 needs a special case, and special cases in index arithmetic are where the bugs live.

Watch it run

Follow the running total being laid down one element at a time, then watch a query resolve as two lookups and a subtraction rather than a walk.

The build is the only linear work that ever happens. Every query afterwards touches exactly two cells, whether the range spans two elements or two million.

The code

from collections import defaultdict

def build_prefix(nums):
    prefix = [0]                       # the leading 0 is not decoration
    for x in nums:
        prefix.append(prefix[-1] + x)
    return prefix

def range_sum(prefix, i, j):           # nums[i..j], inclusive
    return prefix[j + 1] - prefix[i]

nums = [3, -1, 4, 1, -5, 9]
p = build_prefix(nums)
print(p)                                   # [0, 3, 2, 6, 7, 2, 11]
print(range_sum(p, 0, 0), range_sum(p, 1, 3), range_sum(p, 0, 5))
# 3 4 11

Negative numbers are in that example on purpose. Prefix sums do not require the values to be positive, and the running total is allowed to go down — which is exactly what breaks the other common approach to range questions, the sliding window. A window can only shrink from the left when shrinking is guaranteed to help, and with negatives it is not.

The second use is the one that turns up in interviews far more often than the first:

def count_subarrays_summing_to(nums, target):
    """How many subarrays sum to target. One pass, no prefix array stored."""
    seen = defaultdict(int)
    seen[0] = 1                        # the empty prefix, before index 0
    running = total = 0
    for x in nums:
        running += x
        total += seen[running - target]   # every earlier prefix that closes here
        seen[running] += 1
    return total

print(count_subarrays_summing_to([1, 1, 1], 2))                    # 2
print(count_subarrays_summing_to([3, 4, 7, 2, -3, 1, 4, 2], 7))    # 4
print(count_subarrays_summing_to([1, -1, 0], 0))                   # 3

The rearrangement is the whole solution. A subarray ending here sums to target exactly when some earlier prefix equalled running - target. So instead of trying every start index, you ask a hash map how many earlier prefixes had that value — which is the same O(n²)-to-O(n) move as the range query, with a hash table standing in for the array.

The complexity

Build: O(n) time, O(n) space. One addition per element.

Query: O(1). One subtraction, regardless of the range's width.

Total for q queries: O(n + q) instead of O(n·q). State it that way in an interview — the whole argument for precomputation is that the linear cost is paid once rather than per question.

The counting version is O(n) time and O(n) space and never materialises the prefix array at all: it only needs the running total and the map of totals it has already seen.

Where it goes wrong

• Sizing the prefix array at n. Then prefix[j + 1] runs off the end on the last range, and the fix people reach for is a bounds check rather than the leading zero that removes the case entirely.
• Mixing inclusive and exclusive ends. prefix[j] - prefix[i] and prefix[j + 1] - prefix[i] are both correct for some convention. Decide whether j is inclusive before writing a line, and say which one you chose.
• Rebuilding after every update. Prefix sums assume a static array. One write invalidates every later entry, making updates O(n). If the problem mixes updates and queries, the answer is a Fenwick or segment tree, and recognising that boundary is worth more than the prefix implementation itself.
• Using a plain dict and a missing-key crash. defaultdict(int) or dict.get(key, 0); the lookup for a prefix that has never occurred must return zero, not raise.
• Reaching for the sliding window out of habit. For "sum of a range" or "count subarrays with sum k" on data containing negatives, a sliding window is wrong and prefix sums are right. The window needs monotonic growth; the prefix does not.

How to say it in an interview

Two sentences, and the second one is the one that scores:

"I will precompute running totals so each range sum becomes one subtraction — O(n) to build, O(1) per query. For the counting variant I do not even need the array: I keep the running total and a map of how many times each earlier total has occurred, then for each position I look up running - target, which counts every subarray ending here in one step. That is O(n) time and O(n) space, and I seed the map with a zero total seen once so subarrays starting at index 0 are counted."

That last clause is the tell that you have actually run the code, and it costs you four seconds to say.