# Prefix Sums and Difference Arrays — Fast Range Queries and Updates

Source: https://skills101.in/learn/dsa/dsa-prefix-sums-difference-arrays — Skills101 free tutorial (Data Structures & Algorithms). Updated 2026-11-17.

Many problems ask the same kind of question again and again: "what is the sum of the elements from index `l` to `r`?" Adding them up each time costs O(n) per question — too slow when there are 10⁵ questions. A **prefix sum** array answers every such question in **O(1)** after one O(n) pass. Its mirror image, the **difference array**, does the opposite: it applies "add `v` to every element from `l` to `r`" in O(1).

## 1. The prefix sum array

`P[i]` = the sum of the **first `i`** elements. So `P[0] = 0`, `P[1] = a[0]`, `P[2] = a[0] + a[1]`, and so on. `P` has one more cell than `a`.

Then the sum of `a[l..r]` (both ends included) is:

**sum(l, r) = P[r + 1] − P[l]**

![Array a = 3 1 4 1 5 9 2 and its prefix sums P = 0 3 4 8 9 14 23 25; the sum of a[2..5] = P[6] minus P[2] = 23 minus 4 = 19](https://skills101.in/learn-img/dsa/prefix-sum.svg)

```python
def build_prefix(a):
    P = [0]
    for x in a:
        P.append(P[-1] + x)
    return P

a = [3, 1, 4, 1, 5, 9, 2]
P = build_prefix(a)
print(P)

def range_sum(l, r):          # inclusive
    return P[r + 1] - P[l]

print(range_sum(2, 5), range_sum(0, 6), range_sum(3, 3))
```

```text
[0, 3, 4, 8, 9, 14, 23, 25]
19 25 1
```

The extra leading 0 removes every special case: a range that starts at index 0 is just `P[r + 1] − P[0]`.

## 2. Prefix sums + hash map: count subarrays with sum k

**Problem:** count the subarrays whose sum is exactly `k`. The array may contain **negative** numbers, so the sliding window doesn't work.

**Idea:** a subarray `a[l..r]` has sum `k` exactly when `P[r + 1] − P[l] = k`, that is, when an **earlier** prefix sum equals `current − k`. Walk through the array keeping the running sum, and a hash map of how many times each prefix sum has appeared so far.

```python
def count_subarrays(a, k):
    seen = {0: 1}                # the empty prefix has sum 0
    total = count = 0
    for x in a:
        total += x
        count += seen.get(total - k, 0)
        seen[total] = seen.get(total, 0) + 1
    return count

print(count_subarrays([1, 2, 3], 3))
print(count_subarrays([1, -1, 1, -1], 0))
```

```text
2
4
```

For `[1, 2, 3]` and `k = 3` the two subarrays are `[1, 2]` and `[3]`. This runs in **O(n)** time. The same trick solves "longest subarray with sum k" (store the **first** index of each prefix sum) and "subarray sum divisible by k" (store prefix sums **mod k**).

The Java version uses a `HashMap<Long, Integer>`:

```java
import java.util.HashMap;

public class Main {
    static int countSubarrays(int[] a, int k) {
        HashMap<Long, Integer> seen = new HashMap<>();
        seen.put(0L, 1);
        long total = 0;
        int count = 0;
        for (int x : a) {
            total += x;
            count += seen.getOrDefault(total - k, 0);
            seen.merge(total, 1, Integer::sum);
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println(countSubarrays(new int[]{1, 2, 3}, 3));
        System.out.println(countSubarrays(new int[]{1, -1, 1, -1}, 0));
    }
}
```

```text
2
4
```

Use `long` for the running sum: 10⁵ values of 10⁹ add up to 10¹⁴, far beyond `int`.

## 3. 2D prefix sums: sum of any rectangle

For a grid, let `P[i][j]` be the sum of the rectangle from `(0, 0)` to `(i − 1, j − 1)`. Then any rectangle sum is four lookups:

```python
grid = [[1, 2, 3],
        [4, 5, 6],
        [7, 8, 9]]
R, C = len(grid), len(grid[0])
P = [[0] * (C + 1) for _ in range(R + 1)]
for i in range(R):
    for j in range(C):
        P[i + 1][j + 1] = grid[i][j] + P[i][j + 1] + P[i + 1][j] - P[i][j]

def rect(r1, c1, r2, c2):     # inclusive corners
    return P[r2 + 1][c2 + 1] - P[r1][c2 + 1] - P[r2 + 1][c1] + P[r1][c1]

print(rect(1, 1, 2, 2), rect(0, 0, 2, 2), rect(0, 1, 1, 2))
```

```text
28 45 16
```

The `− P[i][j]` (and the `+ P[r1][c1]`) fixes the corner that was added twice — the **inclusion–exclusion** idea.

## 4. Difference arrays: add to a whole range in O(1)

**Problem:** start with zeros, apply many updates "add `v` to every element in `[l, r]`", then print the final array. Doing each update element by element is O(n) per update.

Instead keep a **difference array** `d` (one cell longer than the result). For each update, do just two things: `d[l] += v` and `d[r + 1] −= v`. At the end, a running sum of `d` gives the final values.

![Two updates, add 5 to indexes 1 to 4 and add 2 to indexes 3 to 6, stored as diff = 0 5 0 2 0 -5 0 -2 0; the running sum gives the result 0 5 5 7 7 2 2 0](https://skills101.in/learn-img/dsa/difference-array.svg)

```python
def apply_updates(n, updates):
    d = [0] * (n + 1)
    for l, r, v in updates:
        d[l] += v
        d[r + 1] -= v
    out, run = [], 0
    for i in range(n):
        run += d[i]
        out.append(run)
    return out

print(apply_updates(8, [(1, 4, 5), (3, 6, 2)]))
```

```text
[0, 5, 5, 7, 7, 2, 2, 0]
```

`m` updates on `n` elements now cost **O(n + m)** instead of O(n · m). Real uses: "how many trains are at the station at each minute", "car pooling", "flight bookings", "corporate flight bookings".

## 5. How to recognise these problems

| The problem says… | Reach for |
|---|---|
| many "sum from l to r" questions on a fixed array | prefix sums |
| count / longest subarray with sum k (negatives allowed) | prefix sums + hash map |
| sum of a rectangle in a grid | 2D prefix sums |
| many "add v to a range", then one final read | difference array |
| updates **and** queries mixed together | Fenwick tree or segment tree (later lesson) |

## Common mistakes

- Off-by-one: the sum of `a[l..r]` is `P[r + 1] − P[l]`, not `P[r] − P[l]`.
- Forgetting `seen = {0: 1}`, which misses subarrays that start at index 0.
- Using the sliding window for "subarray sum k" when the array has negatives — it only works for positive numbers.
- Making the difference array length `n` instead of `n + 1`, so `d[r + 1]` falls off the end.
- Overflowing `int` with large prefix sums in Java or C++.

## Quick recap

- `P[i]` = sum of the first `i` items; `sum(l, r) = P[r + 1] − P[l]` in O(1).
- Prefix sum + hash map counts subarrays with sum `k` in O(n), even with negatives.
- 2D prefix sums give any rectangle sum with four lookups.
- Difference array: `d[l] += v`, `d[r + 1] −= v`, then one running sum — O(1) per range update.


Practice quiz and free certificate: https://skills101.in/learn/dsa/dsa-prefix-sums-difference-arrays