Arrays and searching 0/120

Prefix sums · 2 of 3

2D prefix sums

Build a table of block sums for a fixed grid and answer any rectangle sum with four reads.

1,152 words · 6 min read

Part 1 of 4 2D prefix sums

Rectangle sums on a fixed grid

Prefix sums answer questions about a range of an array. The same kind of question comes up on a grid of numbers, where each question names a rectangle of cells and asks for their sum:

You get an m×nm \times n integer matrix once. Write a class NumMatrix whose method sumRegion(row1, col1, row2, col2) returns the sum of the rectangle with top-left corner (row1, col1) and bottom-right corner (row2, col2), both included. Each call must run in O(1)O(1) time.

Constraints

  • 1≤m,n≤2001 \le m, n \le 200
  • −104≤-10^4 \le matrix[i][j] ≤104\le 10^4
  • 0≤0 \le row1 ≤\le row2 <m< m, 0≤0 \le col1 ≤\le col2 <n< n
  • At most 10410^4 calls to sumRegion

Sample · Input

matrix = [[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]
sumRegion(2, 1, 4, 3), sumRegion(1, 1, 2, 2), sumRegion(1, 2, 2, 4)

Output

8, 11, 12

In the sample, sumRegion(1, 1, 2, 2) covers rows 1 to 2 and columns 1 to 2. Those four cells are 6, 3, 2 and 0, and the call returns 11.

Adding up the cells of each rectangle can cost the whole grid per call. The largest grid has 200×200=40,000200 \times 200 = 40{,}000 cells, and there can be 10410^4 calls:

40,000×104=4×108 additions40{,}000 \times 10^4 = 4 \times 10^8 \text{ additions}

That is four times the 10810^8 budget. A prefix array for each row would help: a rectangle would cost one subtraction for each row it covers, up to 200. Over 10410^4 calls that is 2×1062 \times 10^6 steps, which is fast enough for these limits, but the statement asks for O(1)O(1) per call. To get the cost down to a fixed number of reads, the stored sums have to cover rows and columns together.

So we store one sum for every block of cells that starts at the top-left corner of the grid.

Definition

P[r][c] is the sum of the cells in the first r rows and the first c columns of the grid.

Here is the table for the top-left 3 by 3 corner of the sample, taken as a small grid of its own:

grid = [[3, 0, 1],
        [5, 6, 3],
        [1, 2, 0]]

P = [[0, 0,  0,  0],
     [0, 3,  3,  4],
     [0, 8, 14, 18],
     [0, 9, 17, 21]]

P[2][3] = 18 is the first 2 rows and the first 3 columns, 3+0+1+5+6+33 + 0 + 1 + 5 + 6 + 3, and P[3][3] = 21 is the whole grid. The top row and the left column of P are blocks with no rows or no columns, so they hold 0, like prefix[0] in an array. A grid with mm rows and nn columns therefore has a table with m+1m + 1 rows and n+1n + 1 columns.