Prefix Sums for Range Queries and Target Subarrays

Welcome back. In the previous lesson, sorted order justified moving two pointers: each movement safely eliminated candidates. Prefix sums solve a different kind of repeated-work problem. Instead of maintaining an active window, they store the sum of everything seen so far, so a range sum becomes a subtraction.

This lesson covers two closely related interview patterns:

1. Static range-sum queries: preprocess once, then answer each inclusive range query in constant time.
2. Counting subarrays with target sum $k$: combine a running prefix sum with a hash map of previously seen prefix sums.

The second pattern works even when the array contains negative values, where a variable-size sliding window is not generally reliable.

---

1. Prefix sums: store boundaries, not repeated additions

Suppose a backend metric service stores daily net events:

nums = [2, 4, 6, 8, 10]
index   0  1  2  3   4

A request asks for the total from index 1 through index 3, inclusive:

4 + 6 + 8 = 18

One query is trivial. But if the array is static and there are $q$ queries, repeatedly looping from left to right can cost $O(nq)$ in the worst case. The repeated work is the shared prefix: many requests re-add the same early values.

The cleanest convention is to make the prefix array one element longer than the input:

$$P[0]=0$$ $$P[i+1]=P[i]+nums[i]$$

Here, $P[x]$ means “the sum of the first $x$ elements.” It is a boundary sum, not the sum through input index $x$.

For the example:

Boundary / prefix index	0	1	2	3	4	5
P	0	2	6	12	20	30

To sum the inclusive range [left, right], subtract everything before left from everything through right:

$$\mathrm{rangeSum}(left,right)=P[right+1]-P[left]$$

For [1, 3]:

$$P[4]-P[1]=20-2=18$$

The extra initial zero removes the need for a special case when left == 0.

Java implementation for repeated static queries

Use long for stored sums. Even when individual values are int, a large range sum can exceed int.

import java.util.Objects;

public final class PrefixSums {

    private PrefixSums() {
    }

    public static long[] buildPrefixSums(int[] nums) {
        Objects.requireNonNull(nums, "nums must not be null");

        long[] prefix = new long[nums.length + 1];

        for (int i = 0; i < nums.length; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }

        return prefix;
    }

    // Both boundaries are inclusive.
    public static long rangeSum(long[] prefix, int left, int right) {
        Objects.requireNonNull(prefix, "prefix must not be null");

        int inputLength = prefix.length - 1;
        if (left < 0 || right < left || right >= inputLength) {
            throw new IllegalArgumentException("Invalid inclusive range");
        }

        return prefix[right + 1] - prefix[left];
    }
}

Example use:

int[] nums = {2, 4, 6, 8, 10};
long[] prefix = PrefixSums.buildPrefixSums(nums);

long firstElement = PrefixSums.rangeSum(prefix, 0, 0); // 2
long middleRange = PrefixSums.rangeSum(prefix, 1, 3);  // 18
long fullRange = PrefixSums.rangeSum(prefix, 0, 4);    // 30

Complexity and applicability

For an array of length $n$ and $q$ range queries:

Operation	Time	Extra space
Build prefix array	$O(n)$	$O(n)$
One range query	$O(1)$	$O(1)$
All queries	$O(n+q)$	$O(n)$

This is the right pattern when:

• the underlying array is static or changes infrequently;
• the operation is range sum;
• you have many read queries.

If values change frequently, a normal prefix array becomes stale and rebuilding it costs $O(n)$ per update. That is a signal to use a different structure, such as a Fenwick tree or segment tree; for now, keep the scope to static arrays.

---

2. The deeper identity behind a target-sum subarray

Now change the prompt:

Given an integer array nums and an integer k, count the number of contiguous, non-empty subarrays whose sum equals k.

For example:

nums = [1, -1, 1, 1]
k = 1

A brute-force solution chooses every start and end position, then calculates each sum. Without care, that is $O(n^3)$; retaining a sum while extending each chosen start improves it to $O(n^2)$. Still too slow for large inputs.

Prefix sums let us characterize a target subarray algebraically.

For an inclusive subarray from left through right:

$$\mathrm{sum}(left,right)=P[right+1]-P[left]$$

We want that sum to equal $k$:

$$P[right+1]-P[left]=k$$

Rearranging gives:

$$P[left]=P[right+1]-k$$

At each right endpoint, compute the current running prefix sum, call it currentSum. To find a subarray ending at that endpoint with sum k, look for an earlier prefix sum equal to:

$$currentSum-k$$

That is the central interview insight. The prefix before the candidate subarray must have exactly the value that leaves $k$ after subtraction.

---

3. Why a frequency map, rather than a set?

A hash set could tell you whether a required prefix sum exists. But this problem asks you to count all valid subarrays.

Repeated prefix sums matter.

At a current prefix sum of 5, suppose the needed earlier prefix sum is 3, and 3 has occurred twice. Those two occurrences correspond to two distinct possible start boundaries, hence two distinct subarrays ending at the current index.

So maintain:

prefix sum value  ->  number of times it has occurred so far

Initialize the map as:

0 -> 1

This represents the prefix before the first array element. It allows a subarray beginning at index 0 to be counted naturally.

For example, if:

nums = [3, 2]
k = 5

then after both elements, currentSum is 5. We need an earlier prefix of 0. The initialized entry provides it, correctly counting [3, 2].

The required order: look up first, record second

For every value:

1. Add it to currentSum.
2. Add the frequency of currentSum - k to the answer.
3. Record one more occurrence of currentSum.

The ordering is essential. If you record the current sum before checking, then when k == 0, you can accidentally count an empty subarray ending at the current position. The map must represent only prefix boundaries that occurred before the current right boundary.

---

4. Trace the general case, including negatives

Use:

nums = [1, -1, 1, 1]
k = 1

Start with:

currentSum = 0
count = 0
frequencies = {0=1}

Index	Value	currentSum	Needed prefix	Prior frequency	count after lookup
0	1	1	0	1	1
1	-1	0	-1	0	1
2	1	1	0	2	3
3	1	2	1	2	5

The answer is 5.

At index 2, the prefix sum is 1, and prefix sum 0 has been seen twice:

• once before index 0;
• once after index 1.

Those correspond to two target subarrays ending at index 2:

[1, -1, 1]
[1]

This is why storing only whether a prefix exists is insufficient.

Why not use a sliding window here?

A sum-based variable window relies on monotonic behavior:

• expanding the window should only increase the sum;
• shrinking it should only decrease the sum.

That is true when all values are non-negative. It fails in the presence of negatives: adding a negative value may reduce the sum, while removing a negative value may increase it.

The prefix-sum and hash-map approach does not require monotonicity. It works with positive numbers, zeroes, and negative numbers.

---

5. Java implementation: count target-sum subarrays

Use long for both running sum and answer:

• the prefix sum can exceed int;
• the number of valid subarrays can be as high as $O(n^2)$, which can exceed int for realistic constraints.

import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

public static long countSubarraysWithSum(int[] nums, long k) {
    Objects.requireNonNull(nums, "nums must not be null");

    Map<Long, Long> prefixFrequency = new HashMap<>();
    prefixFrequency.put(0L, 1L);

    long currentSum = 0L;
    long count = 0L;

    for (int value : nums) {
        currentSum += value;

        long requiredPrefix = currentSum - k;
        count += prefixFrequency.getOrDefault(requiredPrefix, 0L);

        prefixFrequency.merge(currentSum, 1L, Long::sum);
    }

    return count;
}

A useful test set is:

Input	k	Expected count	What it tests
[1, 1, 1]	2	2	Basic overlapping matches
[1, -1, 1, 1]	1	5	Negatives and repeated prefixes
[0]	0	1	Correct lookup-before-insert order
[3, 2]	5	1	Subarray beginning at index 0
[]	0	0	Empty input

Correctness invariant

At the start of each loop iteration, before processing the next value:

prefixFrequency stores the count of every prefix sum from prior boundaries only, including the virtual empty prefix sum $0$.

After adding the current value, currentSum represents the sum through the current index. Every prior occurrence of currentSum - k identifies exactly one start boundary whose resulting subarray ends at the current index and sums to $k$. Adding that frequency counts all and only those subarrays. Recording currentSum afterward preserves the invariant for later indices.

Complexity

• Time: $O(n)$ expected, because each iteration performs constant-time average hash-map lookup and update.
• Auxiliary space: $O(n)$ in the worst case, when all prefix sums are distinct.

---

Choosing between the two prefix-sum patterns

Prompt signal	Best structure	Core operation
“Many sum queries on an unchanged array”	Prefix array	Subtract two stored boundary sums
“Count subarrays whose sum equals k”	Running prefix sum plus frequency map	Count earlier prefixes equal to currentSum - k
“All values are non-negative; find one shortest/longest valid range”	Often sliding window	Expand and shrink based on a maintained constraint
“Negative values may occur; exact target-sum count”	Prefix sum plus frequency map	Avoid monotonic-window assumptions

An interview-ready explanation for target-sum counting is:

“I maintain a running prefix sum and a map from prior prefix sums to their frequencies. If the current prefix is sum, any prior prefix equal to sum - k defines a subarray ending here with sum k. I add that frequency before recording the current prefix, which prevents empty-subarray counting. This gives expected $O(n)$ time and $O(n)$ space and works even with negative values.”

---

Key takeaways

• A prefix array stores cumulative totals so that an inclusive range sum is:

$$P[right+1]-P[left]$$

• Use a length-$n+1$ prefix array beginning with 0; it removes special handling for ranges starting at index 0.
• For target-sum subarrays, rearrange the range-sum identity to search for an earlier prefix sum equal to:

$$currentSum-k$$

• Use a frequency map, not just a set, because repeated prefix sums produce multiple valid subarrays.
• Initialize the map with 0 -> 1, and always look up before inserting the current prefix sum.
• Prefix-sum counting handles negative values safely, unlike general sum-based sliding windows.

Next, you will move from arrays to intervals, where sorting by start time lets you merge overlapping ranges and justify exactly why the chosen order is correct.