2D Prefix Sums

The 2D prefix-sum trick pads the table by one extra row and one extra column of zeros so range queries never need to special-case the first row or column. Implement prefix(g) for an n x m grid g, returning a (n+1) x (m+1) table p where p[i][j] equals the sum of every g[r][c] with 0 <= r < i and 0 <= c < j, i.e. the sum of the rectangle strictly above and left of the padded cell (i, j).

Row 0 and column 0 of p are therefore all zero, and p[n][m] is the sum of the entire grid. Grid values may be negative.

Example: prefix({{1,2},{3,4}}) returns {{0,0,0}, {0,1,3}, {0,4,10}}.

• p[1][1] = 1: just g[0][0].
• p[1][2] = 3: the top row, g[0][0] + g[0][1] = 1 + 2.
• p[2][2] = 10: the whole grid, 1 + 2 + 3 + 4, confirming p[n][m] is the grid total.

Once p is built, any sub-rectangle sum (rows r1..r2, cols c1..c2) is p[r2+1][c2+1] - p[r1][c2+1] - p[r2+1][c1] + p[r1][c1] in O(1), with no re-scanning.

Input format: each test in tests/*.in is laid out as:

• Line 1: n m, the row and column counts.
• Next n lines: one grid row of m values each.

Test 01.in reads:

1 1
5

This is a 1 x 1 grid holding the single value 5.

Where you'll use it:

• 304. Range Sum Query 2D - Immutable
• 1074. Number of Submatrices That Sum to Target
• 363. Max Sum of Rectangle No Larger Than K
• 1314. Matrix Block Sum