Skills101

AdvancedData Structures & Algorithms · Lesson 19 of 20 · Updated ·

Prefix Sums and Difference Arrays — Fast Range Queries and Updates

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

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))
[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.

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))
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>:

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));
    }
}
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:

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))
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

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)]))
[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 arrayprefix sums
count / longest subarray with sum k (negatives allowed)prefix sums + hash map
sum of a rectangle in a grid2D prefix sums
many "add v to a range", then one final readdifference array
updates and queries mixed togetherFenwick 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 what you learned

📝 Quiz: Prefix Sums and Difference Arrays5 questions · instant answers & explanations · +10 XP · counts towards your free certificateTake the quiz →