Lesson 5.4 · Prefix Sum

2D Prefix Sums

Extend prefix sums to grids with inclusion-exclusion, so any rectangle's sum is four lookups.

12 min

Think of it like this

To find the area of a rectangle cut from a sheet, take the big rectangle from the corner, subtract the strip above and the strip to the left, and add back the small corner you subtracted twice.

1.Building and querying

P[r + 1][c + 1] is the sum of the rectangle from (0, 0) to (r, c). Build: P[r+1][c+1] = m[r][c] + P[r][c+1] + P[r+1][c] − P[r][c].

Sum of rectangle (r1, c1)–(r2, c2) = P[r2+1][c2+1] − P[r1][c2+1] − P[r2+1][c1] + P[r1][c1].

Prefix2D.java

public class Main {
    public static void main(String[] args) {
        int[][] m = {
            {3, 0, 1},
            {5, 6, 3},
            {1, 2, 0}
        };
        int R = m.length, C = m[0].length;
        int[][] P = new int[R + 1][C + 1];
        for (int r = 0; r < R; r++)
            for (int c = 0; c < C; c++)
                P[r + 1][c + 1] = m[r][c] + P[r][c + 1] + P[r + 1][c] - P[r][c];
        // rectangle rows 1..2, cols 1..2: 6 + 3 + 2 + 0
        int r1 = 1, c1 = 1, r2 = 2, c2 = 2;
        System.out.println(P[r2 + 1][c2 + 1] - P[r1][c2 + 1] - P[r2 + 1][c1] + P[r1][c1]);
    }
}

Output

Remember

Use an (R + 1) × (C + 1) table with a zero border.
Rectangle sum = big − top − left + corner.

Common mistakes

Forgetting to add back the corner, subtracting it twice.

Command Palette

2D Prefix Sums

1.Building and querying