Summing any rectangle in one step

Lesson 24 gave you the sum of any stretch of a plain list with one subtraction. For that, it computed prefix sums (running totals) in advance. Grids raise the same question in two dimensions. You have a grid of numbers. What is the total inside a rectangle: a block of pixels, a range of cells in a spreadsheet, an area of a heatmap? The slow way adds up every cell of the rectangle, which costs O(rows × cols) per query (rows is the number of rows, cols the number of columns). With thousands of queries that is hopeless. The 2D prefix sum builds a table once. After that it answers any rectangle of any size with four reads from the table.

Take the grid [[1,2,3],[4,5,6],[7,8,9]] and the question: what is the sum of the bottom-right 2 × 2 square, the numbers 5, 6, 8, 9? You could add them up again for every question. Or you could write down once, in every cell, the sum of the whole rectangle from the grid's top-left corner to that cell.

Then any piece is built from four of those sums. Take the big sum down to the bottom-right corner of the piece. Subtract the strip above the piece. Subtract the strip to the left of the piece. The block above and to the left of the piece was in both strips, so it was subtracted twice. Add it back once. Four numbers, whatever the size of the piece.

In advance, compute one running total for each cell: the sum of the whole rectangle from the grid's top-left corner to that cell. Store these totals in a table P. Add a row of zeros on top of it and a column of zeros on its left. Then the formulas never reach index -1. In this table, P[i+1][j+1] holds the sum from the corner to the cell (i,j).

The table is filled by inclusion-exclusion. The block that ends at (i,j) consists of the cell itself, the block right above it and the block right to its left. Those two blocks overlap in the top-left block, so it was counted twice. Subtract it once:

P[i+1][j+1] = matrix[i][j] + P[i][j+1] + P[i+1][j] - P[i][j]

Once P is built, the sum of a rectangle uses the same idea in reverse. Let the top-left corner of the rectangle be (r1,c1) and the bottom-right corner (r2,c2), both included. Take the big block down to the bottom-right corner. Subtract the strip above the rectangle. Subtract the strip to its left. You just subtracted the top-left block twice, so add it back:

P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]

Trace it on the grid [[1,2,3],[4,5,6],[7,8,9]]. The query is the bottom-right 2 × 2 square, (1,1) to (2,2). It holds the cells 5, 6, 8, 9, total 28. By the formula:

• P[3][3] is the whole grid, 45.
• P[1][3] is the top row, 1 + 2 + 3 = 6.
• P[3][1] is the left column, 1 + 4 + 7 = 12.
• P[1][1] is the top-left cell, 1.

45 - 6 - 12 + 1 = 28. Four reads from the table, whether the rectangle has four cells or four million.

Building P costs O(rows × cols) and happens once. After that each query costs O(1): four reads from the table and three additions or subtractions. For q queries the total is O(rows × cols + q). Adding up the cells again for every query would cost O(q × rows × cols). Memory is O(rows × cols) for the table. The trade is the same as with one-dimensional prefix sums, now in two dimensions: compute once in advance, and then every range question is answered at once.

Integral images in computer vision: fast blurring, feature detection, and finding a small picture inside a bigger one. Totals by area in analytics dashboards and OLAP cubes (multi-dimensional tables for reports). Collision and density queries on a spatial grid. Any sum or average over a rectangle that a user can select. All the lessons on prefix sums lead here. When the same range is queried many times, running totals computed in advance turn each query from a pass over the data into simple arithmetic. Inclusion-exclusion carries the method into two dimensions and beyond.