Prefix Sums Pattern: The Simplest Way to Answer Range Queries Fast

Prefix sums are not flashy, but they unlock a huge class of array problems. If you ever need the sum of many different ranges, recomputing each range from scratch is wasteful. Prefix sums let you pay the cost once and reuse the result.

The idea is small enough to learn in minutes and valuable enough to show up everywhere.

The Basic Idea

Given an array nums, build a new array prefix where:

prefix[i] = sum of the first i elements

That means:

• prefix[0] = 0
• prefix[1] = nums[0]
• prefix[2] = nums[0] + nums[1]

Then any range sum from left to right can be computed as:

prefix[right + 1] - prefix[left]

Example

def build_prefix(nums: list[int]) -> list[int]:
    prefix = [0]
    for num in nums:
        prefix.append(prefix[-1] + num)
    return prefix

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

The extra zero at the front makes the math much cleaner.

Why It Matters

Without prefix sums, a single range query takes O(n) in the worst case.

With prefix sums:

• preprocessing: O(n)
• each query: O(1)

If you have many queries, that is a major improvement.

Prefix Sums + Hash Map

This is where the pattern becomes especially powerful.

Instead of storing prefix sums only in an array, sometimes you track them in a hash map to count how often each prefix has appeared.

Classic example: count the number of subarrays with sum k.

def subarray_sum(nums: list[int], k: int) -> int:
    count = 0
    prefix = 0
    seen = {0: 1}

    for num in nums:
        prefix += num
        count += seen.get(prefix - k, 0)
        seen[prefix] = seen.get(prefix, 0) + 1

    return count

Why does this work?

If the current prefix sum is prefix, then a previous prefix sum of prefix - k means the numbers between those positions sum to k.

Another Important Variant: Equal 0s and 1s

For problems like "longest subarray with equal number of 0s and 1s," you can map:

• 0 -> -1
• 1 -> +1

Then the problem becomes finding the longest subarray with sum 0, which is another prefix sum pattern.

Common Mistakes

• Forgetting the initial 0 prefix
• Mixing inclusive and exclusive range endpoints
• Using sliding window for negative-number subarray sum problems where prefix sums are the correct tool

That last mistake is common. Sliding window works beautifully for positive numbers, but once negatives appear, prefix sums often become the safer choice.

Mental Checklist

Ask yourself:

1. Am I asked about many range sums?
2. Am I counting or detecting subarrays with a target sum?
3. Can I transform the condition into a relationship between two prefix sums?

If yes, prefix sums are probably involved.

Complexity

Practice These Next

• Range Sum Query - Immutable
• Subarray Sum Equals K
• Continuous Subarray Sum
• Find Pivot Index
• Contiguous Array

Prefix sums are one of those patterns that feel almost too simple at first. Then you notice how many harder problems quietly reduce to them.