Prefix sum array: range sums in O(1) and counting subarrays with a hash map

Short answer. A prefix sum array stores the sum of the first i elements in pref[i]. After one O(n) pass, any range sum costs O(1): pref[r + 1] - pref[l]. Use it when sum queries are many and the array does not change. With a hash map it also counts subarrays with a given sum.

What is a prefix sum?

Take an array a. Build an array pref of length n + 1. pref[0] is 0, and pref[i] is the sum of a[0] .. a[i - 1].

The sum of a[l..r] is pref[r + 1] - pref[l]. Everything before l cancels. What remains is exactly the range.

Building costs O(n). Each query after that costs O(1). Without prefixes, each query costs O(n).

When does a problem need prefix sums?

• "Many queries of the form sum of a range."
• "How many subarrays sum to k."
• "Find the index where the left sum equals the right sum."
• "Longest subarray with sum 0", or with equal zeros and ones.

The shared signal: many range sums over a fixed array. If the array changes between queries, reach for a Fenwick tree instead.

What does a prefix sum look like on an example?

Array [2, 4, 1, 3]. pref = [0, 2, 6, 7, 10]. Sum of indexes 1 to 2, which is 4 + 1. pref[3] - pref[1] = 7 - 2 = 5.

Whole array: pref[4] - pref[0] = 10. Empty range: pref[2] - pref[2] = 0. The leading zero removes the special case for l = 0.

How do you write prefix sums in Python?

from itertools import accumulate

def build(a):
    pref = [0]
    for x in a:
        pref.append(pref[-1] + x)
    return pref                      # or list(accumulate(a, initial=0))

def range_sum(pref, l, r):
    return pref[r + 1] - pref[l]     # sum of a[l..r]

def subarray_sum_equals_k(nums, k):
    seen = {0: 1}                    # prefix 0 seen once
    total = count = 0
    for x in nums:
        total += x
        count += seen.get(total - k, 0)
        seen[total] = seen.get(total, 0) + 1
    return count

The third function never stores pref. It only needs the running total and a count of earlier totals.

How does a prefix sum solve Subarray Sum Equals K?

Count subarrays with sum k. The subarray l..r has sum pref[r + 1] - pref[l]. That equals k when pref[l] equals pref[r + 1] - k.

Walk left to right. At each step, count how often the prefix total - k appeared before. That many subarrays end here. Then record the current prefix.

The entry {0: 1} counts subarrays that start at index 0. Without it those go missing.

How do prefix sums compare with the neighbouring patterns?

Pattern	Array changes	Query	Negative numbers
Prefix sums	No	O(1)	Yes
Sliding window	No	O(n) for the whole pass	No, the condition stops being monotonic
Fenwick tree	Yes	O(log n)	Yes
Difference array	Many range additions	O(1) per update	Yes

How do you extend the idea to a matrix?

A 2D prefix pref[i][j] holds the rectangle sum from (0, 0) to (i - 1, j - 1). It builds in O(n · m).

A rectangle sum uses inclusion and exclusion. Subtract the rectangle above and the one to the left. Add back their overlap, which was subtracted twice. Four reads, O(1).

What mistakes break a prefix sum solution?

• A pref of length n instead of n + 1. Sums from index 0 need a special case.
• Recording the current prefix before the lookup. Empty subarrays start counting.
• Forgetting {0: 1} and losing subarrays that start at the front.
• Using prefixes on an array that changes. Each change costs an O(n) rebuild.

How do you explain prefix sums in an interview?

Say: many range sum queries, fixed array. Name pref and the subtraction formula. Give O(n) to build and O(1) per query.

If the task counts subarrays, add the hash map. Say: "I look for the prefix total - k among earlier ones." That sentence is the key.

Drill this pattern on the prefix sums page. The neighbouring trick lives on the difference array page.

FAQ

Do prefix sums work for products or XOR?

Yes, for any operation with an inverse. XOR is its own inverse. Products break on zeros, which need separate handling.

How do you find the index where left sum equals right sum?

Compute the total once. Walk the array with a running left sum. The right sum is total minus left minus the current element. The first match is the answer.

What if the array changes?

Rebuilding after every change is too slow. Use a Fenwick tree: O(log n) per update and per query.

Where do prefix sums show up in real systems?

Analytics: revenue over any period from running totals. Graphics: integral images for fast blur. Databases: range aggregates over sorted data.