060. Two-Dimensional Prefix Queries

Why this mechanism works

A two-dimensional prefix records the rectangle above and left of a boundary. To isolate a query, subtract the unwanted top strip and left strip. Their overlap was subtracted twice, so add it back once. The same inclusion-exclusion principle builds the prefix table.

State and boundaries

prefix[r][c] sums matrix rows before r and columns before c. Its leading row and column are zero boundaries.

Protocol

1. Allocate an extra zero row and column.
2. Build each prefix from top plus left minus shared corner plus current cell.
3. For each query take large prefix minus top minus left plus overlap.
4. Emit the result.

Visualization

P(r2,c2) - P(r1,c2)
          - P(r2,c1) + P(r1,c1)
last term restores the doubly removed corner

Python implementation

def rectangle_sums(matrix, queries):
    rows = len(matrix)
    cols = len(matrix[0]) if rows else 0
    prefix = [[0] * (cols + 1) for _ in range(rows + 1)]
    for r in range(rows):
        for c in range(cols):
            prefix[r + 1][c + 1] = (
                matrix[r][c] + prefix[r][c + 1]
                + prefix[r + 1][c] - prefix[r][c]
            )
    output = []
    for r1, c1, r2, c2 in queries:
        total = (prefix[r2][c2] - prefix[r1][c2]
                 - prefix[r2][c1] + prefix[r1][c1])
        output.append(total)
    return output

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 rectangle_sums: rows = len(matrix)
matrix=[[1, 2, 3], [4, 5, 6]]; queries=[(0, 1, 2, 3), (1, 0, 2, 2), (0, 0, 0, 3)]; rows=2

L3 rectangle_sums: cols = len(matrix[0]) if rows else 0
matrix=[[1, 2, 3], [4, 5, 6]]; queries=[(0, 1, 2, 3), (1, 0, 2, 2), (0, 0, 0, 3)]; rows=2; cols=3

L4 rectangle_sums: prefix = [[0] * (cols + 1) for _ in range(rows + 1)]
matrix=[[1, 2, 3], [4, 5, 6]]; queries=[(0, 1, 2, 3), (1, 0, 2, 2), (0, 0, 0, 3)]; rows=2; cols=3; _=0

L4 rectangle_sums: prefix = [[0] * (cols + 1) for _ in range(rows + 1)]
matrix=[[1, 2, 3], [4, 5, 6]]; queries=[(0, 1, 2, 3), (1, 0, 2, 2), (0, 0, 0, 3)]; rows=2; cols=3; _=1

L4 rectangle_sums: prefix = [[0] * (cols + 1) for _ in range(rows + 1)]
matrix=[[1, 2, 3], [4, 5, 6]]; queries=[(0, 1, 2, 3), (1, 0, 2, 2), (0, 0, 0, 3)]; rows=2; cols=3; _=2

L4 rectangle_sums: prefix = [[0] * (cols + 1) for _ in range(rows + 1)]
matrix=[[1, 2, 3], [4, 5, 6]]; queries=[(0, 1, 2, 3), (1, 0, 2, 2), (0, 0, 0, 3)]; rows=2; cols=3; prefix=[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]

L5 rectangle_sums: for r in range(rows):
matrix=[[1, 2, 3], [4, 5, 6]]; queries=[(0, 1, 2, 3), (1, 0, 2, 2), (0, 0, 0, 3)]; rows=2; cols=3; prefix=[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]; r=0

L6 rectangle_sums: for c in range(cols):
matrix=[[1, 2, 3], [4, 5, 6]]; queries=[(0, 1, 2, 3), (1, 0, 2, 2), (0, 0, 0, 3)]; rows=2; cols=3; prefix=[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]; r=0; c=0

... 18 intermediate state changes omitted ...

L15 rectangle_sums: output.append(total)
matrix=[[1, 2, 3], [4, 5, 6]]; queries=[(0, 1, 2, 3), (1, 0, 2, 2), (0, 0, 0, 3)]; rows=2; cols=3; prefix=[[0, 0, 0, 0], [0, 1, 3, 6], [0, 5, 12, 21]]; r=1; c=2; output=[16, 9]; r1=1; c1=0; r2=2; c2=2; total=9

L12 rectangle_sums: for r1, c1, r2, c2 in queries:
matrix=[[1, 2, 3], [4, 5, 6]]; queries=[(0, 1, 2, 3), (1, 0, 2, 2), (0, 0, 0, 3)]; rows=2; cols=3; prefix=[[0, 0, 0, 0], [0, 1, 3, 6], [0, 5, 12, 21]]; r=1; c=2; output=[16, 9]; r1=0; c1=0; r2=0; c2=3; total=9

L13 rectangle_sums: total = (prefix[r2][c2] - prefix[r1][c2]
matrix=[[1, 2, 3], [4, 5, 6]]; queries=[(0, 1, 2, 3), (1, 0, 2, 2), (0, 0, 0, 3)]; rows=2; cols=3; prefix=[[0, 0, 0, 0], [0, 1, 3, 6], [0, 5, 12, 21]]; r=1; c=2; output=[16, 9]; r1=0; c1=0; r2=0; c2=3; total=0

L15 rectangle_sums: output.append(total)
matrix=[[1, 2, 3], [4, 5, 6]]; queries=[(0, 1, 2, 3), (1, 0, 2, 2), (0, 0, 0, 3)]; rows=2; cols=3; prefix=[[0, 0, 0, 0], [0, 1, 3, 6], [0, 5, 12, 21]]; r=1; c=2; output=[16, 9, 0]; r1=0; c1=0; r2=0; c2=3; total=0

L2 rectangle_sums: rows = len(matrix)
matrix=[]; queries=[(0, 0, 0, 0)]; rows=0

L3 rectangle_sums: cols = len(matrix[0]) if rows else 0
matrix=[]; queries=[(0, 0, 0, 0)]; rows=0; cols=0

L4 rectangle_sums: prefix = [[0] * (cols + 1) for _ in range(rows + 1)]
matrix=[]; queries=[(0, 0, 0, 0)]; rows=0; cols=0; _=0

L4 rectangle_sums: prefix = [[0] * (cols + 1) for _ in range(rows + 1)]
matrix=[]; queries=[(0, 0, 0, 0)]; rows=0; cols=0; prefix=[[0]]

L11 rectangle_sums: output = []
matrix=[]; queries=[(0, 0, 0, 0)]; rows=0; cols=0; prefix=[[0]]; output=[]

L12 rectangle_sums: for r1, c1, r2, c2 in queries:
matrix=[]; queries=[(0, 0, 0, 0)]; rows=0; cols=0; prefix=[[0]]; output=[]; r1=0; c1=0; r2=0; c2=0

L13 rectangle_sums: total = (prefix[r2][c2] - prefix[r1][c2]
matrix=[]; queries=[(0, 0, 0, 0)]; rows=0; cols=0; prefix=[[0]]; output=[]; r1=0; c1=0; r2=0; c2=0; total=0

L15 rectangle_sums: output.append(total)
matrix=[]; queries=[(0, 0, 0, 0)]; rows=0; cols=0; prefix=[[0]]; output=[0]; r1=0; c1=0; r2=0; c2=0; total=0

Why the solution is correct

The construction formula counts each cell in the represented rectangle once. The query formula removes exactly the cells outside the requested row and column bounds, adding back the doubly removed corner. Thus only the requested rectangle remains.

Time and space

O(rows*cols+q) time and O(rows*cols+q) storage including answers; each query is O(1).

Common mistakes

Omitting the added-back corner double-subtracts it. Using matrix coordinates directly in the prefix table forgets the leading boundary row and column.

Reasoning card

Transfer exercise

Describe the four corner updates needed for adding a value to many rectangles in a two-dimensional difference array.