PK

PKBytes

Explore tracks
Chapter 10: Matrices, Grids and Multidimensional Arrays
10.05Beginner / Intermediate4 topics14 min4 interactive animations

2D prefix and difference

2D prefix sums answer any submatrix sum in O(1) after an O(R·C) build, and 2D difference arrays apply many rectangle updates in O(1) each. Both rely on inclusion-exclusion over four corners.

Learning goals

  • Build a 2D prefix sum table
  • Answer submatrix queries with four lookups
  • Apply rectangle updates with four corner edits

Prerequisites

Prefix and suffix methodsNeighbourhood reasoning
10.05.1

2D prefix sums

Let p[r][c] be the sum of all cells in rows 0..r-1 and columns 0..c-1, with an extra row and column of zeros. Then p[r][c] = g[r-1][c-1] + p[r-1][c] + p[r][c-1] - p[r-1][c-1]: the cell, the block above, the block to the left, minus the overlap that both counted. The build is O(R·C).

Watch the table fill; each step shows the overlap being subtracted.

Java
1int R = g.length, C = g[0].length;
2long[][] p = new long[R + 1][C + 1];
3for (int r = 1; r <= R; r++)
4    for (int c = 1; c <= C; c++)
5        p[r][c] = g[r - 1][c - 1] + p[r - 1][c] + p[r][c - 1] - p[r - 1][c - 1];

2D prefix sums and submatrix queries

Interactive · edit the input

Your input

Try

grid · 4 × 5

01234
0
0
0
0
0
0
1
0
0
0
0
0
2
0
0
0
0
0
3
0
0
0
0
0
Cell being builtBuiltCorner used in the query
Setup

The prefix matrix has one extra row and column of zeros, so every query formula works without special cases.

Step 1 / 14
Java
1int[][] p = new int[R + 1][C + 1];                       // p[r][c] = sum of g[0..r-1][0..c-1]
2for (int r = 1; r <= R; r++)
3    for (int c = 1; c <= C; c++)
4        p[r][c] = g[r - 1][c - 1] + p[r - 1][c] + p[r][c - 1] - p[r - 1][c - 1];   // inclusion-exclusion
5static int sum(int[][] p, int r1, int c1, int r2, int c2) {          // inclusive corners
6    return p[r2 + 1][c2 + 1] - p[r1][c2 + 1] - p[r2 + 1][c1] + p[r1][c1];
7}

Live state

R

3

C

4

No condition evaluated on this step
Execution trace (dry run table)Show 14 steps
StepLineStateWhat happens
1L1R=3 C=4The prefix matrix has one extra row and column of zeros, so every query formula works without special cases.
2L4r=1 c=1 g[r-1][c-1]=3 p[r][c]=3p[1][1] = 3 + above 0 + left 0 - overlap 0 = 3. The overlap was counted twice, so subtract it once.
3L4r=1 c=2 g[r-1][c-1]=0 p[r][c]=3p[1][2] = 0 + above 0 + left 3 - overlap 0 = 3. The overlap was counted twice, so subtract it once.
4L4r=1 c=3 g[r-1][c-1]=1 p[r][c]=4p[1][3] = 1 + above 0 + left 3 - overlap 0 = 4. The overlap was counted twice, so subtract it once.
5L4r=1 c=4 g[r-1][c-1]=4 p[r][c]=8p[1][4] = 4 + above 0 + left 4 - overlap 0 = 8. The overlap was counted twice, so subtract it once.
6L4r=2 c=1 g[r-1][c-1]=2 p[r][c]=5p[2][1] = 2 + above 3 + left 0 - overlap 0 = 5. The overlap was counted twice, so subtract it once.
7L4r=2 c=2 g[r-1][c-1]=5 p[r][c]=10p[2][2] = 5 + above 3 + left 5 - overlap 3 = 10. The overlap was counted twice, so subtract it once.
8L4r=2 c=3 g[r-1][c-1]=6 p[r][c]=17p[2][3] = 6 + above 4 + left 10 - overlap 3 = 17. The overlap was counted twice, so subtract it once.
9L4r=2 c=4 g[r-1][c-1]=3 p[r][c]=24p[2][4] = 3 + above 8 + left 17 - overlap 4 = 24. The overlap was counted twice, so subtract it once.
10L4r=3 c=1 g[r-1][c-1]=2 p[r][c]=7p[3][1] = 2 + above 5 + left 0 - overlap 0 = 7. The overlap was counted twice, so subtract it once.
11L4r=3 c=2 g[r-1][c-1]=1 p[r][c]=13p[3][2] = 1 + above 10 + left 7 - overlap 5 = 13. The overlap was counted twice, so subtract it once.
12L4r=3 c=3 g[r-1][c-1]=1 p[r][c]=21p[3][3] = 1 + above 17 + left 13 - overlap 10 = 21. The overlap was counted twice, so subtract it once.
13L4r=3 c=4 g[r-1][c-1]=5 p[r][c]=33p[3][4] = 5 + above 24 + left 21 - overlap 17 = 33. The overlap was counted twice, so subtract it once.
14L6query=(1,1) to (2,2) return=13Sum of the rectangle (1,1) to (2,2) = p[3][3] - p[1][3] - p[3][1] + p[1][1] = 21 - 4 - 7 + 3 = 13. Each query is O(1) after the O(R x C) build.
10.05.2

Submatrix sums

The sum of the rectangle from (r1, c1) to (r2, c2), inclusive, is p[r2+1][c2+1] - p[r1][c2+1] - p[r2+1][c1] + p[r1][c1]: take the big block, remove the strip above and the strip to the left, and add back the corner that was removed twice. Each query is four lookups, O(1).

Choose the corner cells in the animation; the four used entries are highlighted.

Java
1static long sum(long[][] p, int r1, int c1, int r2, int c2) {          // inclusive corners
2    return p[r2 + 1][c2 + 1] - p[r1][c2 + 1] - p[r2 + 1][c1] + p[r1][c1];
3}

2D prefix sums and submatrix queries

Interactive · edit the input

Your input

Try

grid · 4 × 5

01234
0
0
0
0
0
0
1
0
0
0
0
0
2
0
0
0
0
0
3
0
0
0
0
0
Cell being builtBuiltCorner used in the query
Setup

The prefix matrix has one extra row and column of zeros, so every query formula works without special cases.

Step 1 / 14
Java
1int[][] p = new int[R + 1][C + 1];                       // p[r][c] = sum of g[0..r-1][0..c-1]
2for (int r = 1; r <= R; r++)
3    for (int c = 1; c <= C; c++)
4        p[r][c] = g[r - 1][c - 1] + p[r - 1][c] + p[r][c - 1] - p[r - 1][c - 1];   // inclusion-exclusion
5static int sum(int[][] p, int r1, int c1, int r2, int c2) {          // inclusive corners
6    return p[r2 + 1][c2 + 1] - p[r1][c2 + 1] - p[r2 + 1][c1] + p[r1][c1];
7}

Live state

R

3

C

4

No condition evaluated on this step
Execution trace (dry run table)Show 14 steps
StepLineStateWhat happens
1L1R=3 C=4The prefix matrix has one extra row and column of zeros, so every query formula works without special cases.
2L4r=1 c=1 g[r-1][c-1]=3 p[r][c]=3p[1][1] = 3 + above 0 + left 0 - overlap 0 = 3. The overlap was counted twice, so subtract it once.
3L4r=1 c=2 g[r-1][c-1]=0 p[r][c]=3p[1][2] = 0 + above 0 + left 3 - overlap 0 = 3. The overlap was counted twice, so subtract it once.
4L4r=1 c=3 g[r-1][c-1]=1 p[r][c]=4p[1][3] = 1 + above 0 + left 3 - overlap 0 = 4. The overlap was counted twice, so subtract it once.
5L4r=1 c=4 g[r-1][c-1]=4 p[r][c]=8p[1][4] = 4 + above 0 + left 4 - overlap 0 = 8. The overlap was counted twice, so subtract it once.
6L4r=2 c=1 g[r-1][c-1]=2 p[r][c]=5p[2][1] = 2 + above 3 + left 0 - overlap 0 = 5. The overlap was counted twice, so subtract it once.
7L4r=2 c=2 g[r-1][c-1]=5 p[r][c]=10p[2][2] = 5 + above 3 + left 5 - overlap 3 = 10. The overlap was counted twice, so subtract it once.
8L4r=2 c=3 g[r-1][c-1]=6 p[r][c]=17p[2][3] = 6 + above 4 + left 10 - overlap 3 = 17. The overlap was counted twice, so subtract it once.
9L4r=2 c=4 g[r-1][c-1]=3 p[r][c]=24p[2][4] = 3 + above 8 + left 17 - overlap 4 = 24. The overlap was counted twice, so subtract it once.
10L4r=3 c=1 g[r-1][c-1]=2 p[r][c]=7p[3][1] = 2 + above 5 + left 0 - overlap 0 = 7. The overlap was counted twice, so subtract it once.
11L4r=3 c=2 g[r-1][c-1]=1 p[r][c]=13p[3][2] = 1 + above 10 + left 7 - overlap 5 = 13. The overlap was counted twice, so subtract it once.
12L4r=3 c=3 g[r-1][c-1]=1 p[r][c]=21p[3][3] = 1 + above 17 + left 13 - overlap 10 = 21. The overlap was counted twice, so subtract it once.
13L4r=3 c=4 g[r-1][c-1]=5 p[r][c]=33p[3][4] = 5 + above 24 + left 21 - overlap 17 = 33. The overlap was counted twice, so subtract it once.
14L6query=(1,1) to (2,2) return=13Sum of the rectangle (1,1) to (2,2) = p[3][3] - p[1][3] - p[3][1] + p[1][1] = 21 - 4 - 7 + 3 = 13. Each query is O(1) after the O(R x C) build.
10.05.3

2D difference arrays

A 2D difference array is the inverse of a 2D prefix sum: d is chosen so that taking its 2D prefix sum yields the grid. Adding v to a whole rectangle then changes only four cells of d, and one prefix-sum pass at the end produces the final grid. It makes m updates cost O(m + R·C) instead of O(m·R·C).

Enter several updates as r1, c1, r2, c2, v and watch four corners change per update.

Java
1int[][] d = new int[n + 1][n + 1];
2for (int[] u : updates) {                    // u = {r1, c1, r2, c2, v}
3    d[u[0]][u[1]] += u[4];
4    d[u[0]][u[3] + 1] -= u[4];
5    d[u[2] + 1][u[1]] -= u[4];
6    d[u[2] + 1][u[3] + 1] += u[4];
7}

2D difference array: rectangle updates

Interactive · edit the input

Your input

Try

grid · 4 × 4

0123
0
0
0
0
0
1
0
0
0
0
2
0
0
0
0
3
0
0
0
0
Corner being editedCell rebuiltCorner already edited
Setup

The difference grid d is 4 x 4. Each rectangle update touches only four corners, however large the rectangle is.

Step 1 / 13
Java
1int[][] d = new int[n + 1][n + 1];
2for (int[] u : updates) {                       // u = {r1, c1, r2, c2, v}
3    d[u[0]][u[1]] += u[4];
4    d[u[0]][u[3] + 1] -= u[4];
5    d[u[2] + 1][u[1]] -= u[4];
6    d[u[2] + 1][u[3] + 1] += u[4];             // four corners instead of the whole rectangle
7}
8// rebuild: a 2D prefix sum of d gives the final grid
9for (int r = 0; r < n; r++) for (int c = 0; c < n; c++) {
10    g[r][c] = d[r][c] + (r > 0 ? g[r - 1][c] : 0) + (c > 0 ? g[r][c - 1] : 0) - (r > 0 && c > 0 ? g[r - 1][c - 1] : 0);
11}

Live state

n

3

No condition evaluated on this step
Execution trace (dry run table)Show 13 steps
StepLineStateWhat happens
1L1n=3The difference grid d is 4 x 4. Each rectangle update touches only four corners, however large the rectangle is.
2L6update=(0,0)-(1,1) +2Add 2 to the rectangle (0,0) to (1,1): +2 at (0,0), -2 at (0,2), -2 at (2,0), +2 at (2,2).
3L6update=(1,1)-(2,2) +3Add 3 to the rectangle (1,1) to (2,2): +3 at (1,1), -3 at (1,3), -3 at (3,1), +3 at (3,3).
4L10r=0 c=0 g[r][c]=2g[0][0] = d[0][0] + above + left - overlap = 2.
5L10r=0 c=1 g[r][c]=2g[0][1] = d[0][1] + above + left - overlap = 2.
6L10r=0 c=2 g[r][c]=0g[0][2] = d[0][2] + above + left - overlap = 0.
7L10r=1 c=0 g[r][c]=2g[1][0] = d[1][0] + above + left - overlap = 2.
8L10r=1 c=1 g[r][c]=5g[1][1] = d[1][1] + above + left - overlap = 5.
9L10r=1 c=2 g[r][c]=3g[1][2] = d[1][2] + above + left - overlap = 3.
10L10r=2 c=0 g[r][c]=0g[2][0] = d[2][0] + above + left - overlap = 0.
11L10r=2 c=1 g[r][c]=3g[2][1] = d[2][1] + above + left - overlap = 3.
12L10r=2 c=2 g[r][c]=3g[2][2] = d[2][2] + above + left - overlap = 3.
13L11return=[[2, 2, 0], [2, 5, 3], [0, 3, 3]]2 updates applied in O(1) each plus one O(n²) rebuild, instead of O(n²) per update.
10.05.4

Rectangular range updates

To rebuild after the updates, take the 2D prefix sum of d: g[r][c] = d[r][c] + g[r-1][c] + g[r][c-1] - g[r-1][c-1]. Each corner edit propagates over the whole rectangle to its lower right and is cancelled by the opposite corners at the rectangle's edge. This is the 2D version of the Imos method.

Overlapping rectangles simply add.

Java
1int[][] g = new int[n][n];
2for (int r = 0; r < n; r++)
3    for (int c = 0; c < n; c++)
4        g[r][c] = d[r][c] + (r > 0 ? g[r - 1][c] : 0) + (c > 0 ? g[r][c - 1] : 0) - (r > 0 && c > 0 ? g[r - 1][c - 1] : 0);

2D difference array: rectangle updates

Interactive · edit the input

Your input

Try

grid · 4 × 4

0123
0
0
0
0
0
1
0
0
0
0
2
0
0
0
0
3
0
0
0
0
Corner being editedCell rebuiltCorner already edited
Setup

The difference grid d is 4 x 4. Each rectangle update touches only four corners, however large the rectangle is.

Step 1 / 13
Java
1int[][] d = new int[n + 1][n + 1];
2for (int[] u : updates) {                       // u = {r1, c1, r2, c2, v}
3    d[u[0]][u[1]] += u[4];
4    d[u[0]][u[3] + 1] -= u[4];
5    d[u[2] + 1][u[1]] -= u[4];
6    d[u[2] + 1][u[3] + 1] += u[4];             // four corners instead of the whole rectangle
7}
8// rebuild: a 2D prefix sum of d gives the final grid
9for (int r = 0; r < n; r++) for (int c = 0; c < n; c++) {
10    g[r][c] = d[r][c] + (r > 0 ? g[r - 1][c] : 0) + (c > 0 ? g[r][c - 1] : 0) - (r > 0 && c > 0 ? g[r - 1][c - 1] : 0);
11}

Live state

n

3

No condition evaluated on this step
Execution trace (dry run table)Show 13 steps
StepLineStateWhat happens
1L1n=3The difference grid d is 4 x 4. Each rectangle update touches only four corners, however large the rectangle is.
2L6update=(0,0)-(1,1) +2Add 2 to the rectangle (0,0) to (1,1): +2 at (0,0), -2 at (0,2), -2 at (2,0), +2 at (2,2).
3L6update=(1,1)-(2,2) +3Add 3 to the rectangle (1,1) to (2,2): +3 at (1,1), -3 at (1,3), -3 at (3,1), +3 at (3,3).
4L10r=0 c=0 g[r][c]=2g[0][0] = d[0][0] + above + left - overlap = 2.
5L10r=0 c=1 g[r][c]=2g[0][1] = d[0][1] + above + left - overlap = 2.
6L10r=0 c=2 g[r][c]=0g[0][2] = d[0][2] + above + left - overlap = 0.
7L10r=1 c=0 g[r][c]=2g[1][0] = d[1][0] + above + left - overlap = 2.
8L10r=1 c=1 g[r][c]=5g[1][1] = d[1][1] + above + left - overlap = 5.
9L10r=1 c=2 g[r][c]=3g[1][2] = d[1][2] + above + left - overlap = 3.
10L10r=2 c=0 g[r][c]=0g[2][0] = d[2][0] + above + left - overlap = 0.
11L10r=2 c=1 g[r][c]=3g[2][1] = d[2][1] + above + left - overlap = 3.
12L10r=2 c=2 g[r][c]=3g[2][2] = d[2][2] + above + left - overlap = 3.
13L11return=[[2, 2, 0], [2, 5, 3], [0, 3, 3]]2 updates applied in O(1) each plus one O(n²) rebuild, instead of O(n²) per update.

Practice ladder

Now try it yourself

Easy

  • Build the prefix table of [[1, 2], [3, 4]]
  • How many table lookups does one submatrix query need?

Medium

  • Find the sum of the rectangle from (1, 1) to (2, 2) of a 3 × 3 grid using prefix sums
  • Apply two overlapping rectangle updates with a difference array

Advanced

  • Find the maximum-sum k × k square in O(R·C) using 2D prefix sums

Key takeaways

  • p[r][c] = cell + above + left - overlap; a query is p(big) - p(top) - p(left) + p(corner).
  • Rectangle updates touch four corners; one prefix-sum pass rebuilds the grid.
  • Use long for the sums when values or sizes are large.