# Prefix Sums — Part 1: The Pattern

A prefix sum array stores running totals so that **the sum of any range is one subtraction**: `sum(i..j) = prefix[j+1] − prefix[i]`. Combined with a hash map of previously seen prefix sums, it answers "how many subarrays have sum k?" in O(n), and unlike sliding windows it works with **negative numbers**.

![A prefix array where the sum of a range is the difference of two prefix values](diagrams/01-prefix-sums.svg)

## 1. Recognition Cues

- "sum of elements between i and j", many range queries on a static array
- "number of subarrays with sum equal to k", "subarray sum divisible by k", "equal number of 0s and 1s"
- "pivot/equilibrium index" (left sum equals right sum)
- 2D: "sum of a sub-rectangle", many rectangle queries on a matrix

## 2. Templates

```typescript
function buildPrefix(nums: number[]): number[] {
  const prefix = new Array(nums.length + 1).fill(0);
  for (let i = 0; i < nums.length; i++) prefix[i + 1] = prefix[i] + nums[i];
  return prefix;
}

function countSubarraysWithSum(nums: number[], k: number): number {
  const seen = new Map<number, number>([[0, 1]]);
  let running = 0, count = 0;
  for (const x of nums) {
    running += x;
    count += seen.get(running - k) ?? 0;
    seen.set(running, (seen.get(running) ?? 0) + 1);
  }
  return count;
}
```

```python
def build_prefix(nums):
    prefix = [0] * (len(nums) + 1)          # prefix[i] = sum of nums[0:i]
    for i, x in enumerate(nums):
        prefix[i + 1] = prefix[i] + x
    return prefix                           # sum(i..j) = prefix[j+1] - prefix[i]

def count_subarrays_with_sum(nums, k):
    seen = {0: 1}                           # prefix sum -> how many times seen
    running = count = 0
    for x in nums:
        running += x
        count += seen.get(running - k, 0)   # earlier prefixes that leave sum k
        seen[running] = seen.get(running, 0) + 1
    return count
```

The `seen = {0: 1}` initialization represents the empty prefix, so subarrays starting at index 0 are counted.

## 3. Why Prefix + Hash Map Works

If the running sum at index j is `P[j]`, a subarray `(i..j]` sums to k exactly when `P[i] = P[j] − k`. So at each j, the number of valid subarrays ending at j is **the number of earlier prefixes equal to `P[j] − k`**, which a hash map counts in O(1).

Variants change what you store or look up:

| Problem | Transform | Map stores |
|---|---|---|
| subarray sum = k | none | prefix → count |
| longest subarray with sum k | none | prefix → **first** index |
| equal 0s and 1s | map 0 → −1, find sum 0 | prefix → first index |
| sum divisible by k | use `prefix % k` (normalize negatives) | remainder → count |

## 4. 2D Prefix Sums

For a matrix, `P[r+1][c+1]` = sum of the rectangle from `(0,0)` to `(r,c)`:

```text
P[r+1][c+1] = M[r][c] + P[r][c+1] + P[r+1][c] − P[r][c]
sum(r1..r2, c1..c2) = P[r2+1][c2+1] − P[r1][c2+1] − P[r2+1][c1] + P[r1][c1]
```

Building costs O(R·C); every rectangle query is then O(1). This is inclusion–exclusion: add the two overlapping strips, subtract the doubly counted corner.

## 5. Related: Difference Arrays

The inverse trick: to add `v` to every element in `[l, r]` many times, write `diff[l] += v` and `diff[r+1] −= v`, then take one prefix sum at the end. Range updates become O(1) each (car pooling, corporate flight bookings).

## Common Pitfalls

1. **Forgetting `{0: 1}`** (or index −1 for "first index" variants), which misses subarrays starting at 0.
2. **Updating the map before querying it**, which counts the empty subarray when k = 0.
3. **Negative remainders:** in Python `-1 % 5 == 4`, but in JS/C# `-1 % 5 == -1`; normalize with `((x % k) + k) % k`.
4. **Integer overflow** in C#/Java with large sums: use `long`.
5. **Using a sliding window** when numbers can be negative.

## Quick Reference

```text
prefix[i+1] = prefix[i] + a[i];  sum(i..j) = prefix[j+1] - prefix[i]
count sum=k: seen={0:1}; run+=x; ans+=seen[run-k]; seen[run]++
2D: P[r+1][c+1] = M[r][c] + P[r][c+1] + P[r+1][c] - P[r][c]
diff array: diff[l]+=v; diff[r+1]-=v; prefix at the end
```