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 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 time.
Constraints
-
matrix[i][j] -
row1row2,col1col2 - At most 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 cells, and there can be calls:
That is four times the budget. A prefix array for each row would help: a rectangle would cost one subtraction for each row it covers, up to 200. Over calls that is steps, which is fast enough for these limits, but the statement asks for 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, , 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 rows and columns therefore has a table with rows and columns.
Answer a rectangle with four reads
Now let's get the sum of rows 1 to 2 and columns 1 to 2 of the small grid, the cells 6, 3, 2 and 0, out of P. We start from P[3][3] = 21, which covers the rectangle together with the row above it and the column to its left. P[1][3] = 4 is that row above, across the full width, and P[3][1] = 9 is that column to the left, down the full height. Subtracting both removes everything outside the rectangle. But the cell 3 in the grid's top-left corner lies in that row and in that column, so it has been removed twice, and P[1][1] = 3 puts it back once:
For the general rule, we write the rectangle with half-open bounds, which include the first index and stop just before the second: rows [r1, r2) and columns [c1, c2), where r2 and c2 are the row and the column just past the rectangle. Its sum is
P[r2][c2] - P[r1][c2] - P[r2][c1] + P[r1][c1]The first entry is the block that ends at the rectangle's bottom-right corner. The next two remove the rows above the rectangle and the columns to its left. The last adds back the block above and to the left, which both of them removed. In the example, rows [1, 3) and columns [1, 3) read P[3][3], P[1][3], P[3][1] and P[1][1].
Step through the four reads
The widget applies the four reads one at a time to the same rectangle. Each cell shows how many times the reads so far have counted it, so you can watch the grid's top-left cell drop to after the two subtractions and return to 0 on the last read.
Then move the sliders to try other rectangles. One that starts at row 0 has no rows above it, and the two entries read for those rows, P[0][c2] and P[0][c1], are both 0.
Fill the table in one pass
Filling the table uses the same idea of an overlap that is counted twice. Say we are filling P[r + 1][c + 1], the block whose bottom-right cell is matrix[r][c]. Leave out the block's last row and you have P[r][c + 1]. Leave out its last column and you have P[r + 1][c]. Added together, those two cover every cell of the block except matrix[r][c], and they cover the cells of P[r][c] twice. So we add the cell and subtract P[r][c] once:
In the small grid, P[2][2] is , the sum of 3, 0, 5 and 6. If we fill the table row by row, from left to right, the three entries on the right-hand side are always filled before they are needed.
The class fills P in its constructor. sumRegion receives the last row and the last column of the rectangle, both included, so it adds 1 to each to get r2 and c2:
class NumMatrix:
def __init__(self, matrix):
rows, cols = len(matrix), len(matrix[0])
self.P = [[0] * (cols + 1) for _ in range(rows + 1)]
for r in range(rows):
for c in range(cols):
self.P[r + 1][c + 1] = (matrix[r][c] + self.P[r][c + 1]
+ self.P[r + 1][c] - self.P[r][c])
def sumRegion(self, row1, col1, row2, col2):
P = self.P
return (P[row2 + 1][col2 + 1] - P[row1][col2 + 1]
- P[row2 + 1][col1] + P[row1][col1])
m = NumMatrix([[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]])
print(m.sumRegion(2, 1, 4, 3))
print(m.sumRegion(1, 1, 2, 2))
print(m.sumRegion(1, 2, 2, 4))In the full sample, sumRegion(1, 1, 2, 2) reads P[3][3] - P[1][3] - P[3][1] + P[1][1]. These are the four entries from the small grid, which is the top-left corner of the full one, so the call returns .
Cost of rectangle sums
- Adding up each rectangle cell by cell
per call - Up to 40,000 cells per call, which is additions over calls.
- One prefix array per row
per call - After an pass to build the row arrays, one subtraction for each row of the rectangle, up to 200.
- Filling the table
, once - One formula per cell, 40,000 at the largest size, and numbers of memory.
- Each call after that
- Four reads, so calls cost 40,000 reads.
Common 2D prefix-sum mistakes
Forgetting to add the top-left block back.
- Where it breaks
- For rows
[1, 3)and columns[1, 3)of the small grid, instead of 11: the cell 3 at(0, 0)was subtracted twice. - The fix
- Add
P[r1][c1]in the query, and subtractP[r][c]when filling the table, where the same overlap is counted twice.
Reading the inclusive corner as the half-open bounds.
- Where it breaks
sumRegion(1, 1, 2, 2)read asP[2][2] - P[1][2] - P[2][1] + P[1][1]gives , the cell(1, 1)alone, instead of 11.- The fix
- Add 1 to
row2andcol2before readingP.
Recall A rectangle starts at row 0 and column 0. Which of the four reads are zero, and what is left?
With r1 = 0 and c1 = 0, the entries P[0][c2], P[r2][0] and P[0][0] all lie in the row or the column of zeros. Three reads vanish and the sum is P[r2][c2] alone, which is how P was defined: the sum of the first r2 rows and the first c2 columns.