Matrix Block Sum

Matrix Block Sum is the 2-D version of the running-sum trick. It teaches the move that makes any rectangle (or square block) sum a constant-time lookup: a 2-D prefix table plus a four-corner formula, with bounds clamped so the block never falls off the edge of the grid.

The slow way first

The obvious idea: for every cell, loop over its (2k+1) x (2k+1) block and add the values. That is O(m·n·k²) — for each of the m·n cells we re-scan up to k² neighbors. When k is large the same values get added over and over.

The question to ask: can I answer "what is the sum of this rectangle?" without walking the rectangle? If I precompute the sum of every top-left rectangle, then any block sum is just a little arithmetic on four of those precomputed values.

The idea: a 2-D prefix table

Build a table P of size (m+1) x (n+1) where P[i+1][j+1] is the sum of every element in the rectangle from (0, 0) to (i, j). The extra zero row and zero column (the padding) let the corner formula read index 0 without going out of bounds.

Each entry is filled with P[i+1][j+1] = mat[i][j] + P[i][j+1] + P[i+1][j] - P[i][j] (add the cell, add the rectangle above, add the rectangle to the left, and subtract the part counted twice). Then a block sum from (r1, c1) to (r2, c2) is read from four corners.

The key insight: the block bounds are clamped with max(0, i-k) and min(m-1, i+k) so a center near an edge simply uses a smaller window — no special cases, no out-of-bounds reads.

Walk through it

Step through the animation. First the prefix table P fills in cell by cell using the four-term formula (its green zero border is known up front). Then we pick center cell (1, 1), clamp the bounds to r1=0, c1=0, r2=2, c2=2, and read the four corners P[3][3] - P[0][3] - P[3][0] + P[0][0] = 45 - 0 - 0 + 0 = 45.

Pseudocode

build P of size (m+1) x (n+1), all zeros        # the zero border is the padding
for each cell (i, j) in mat:
    P[i+1][j+1] = mat[i][j] + above + left - diagonal
 
for each cell (i, j):
    r1 = max(0, i - k);  c1 = max(0, j - k)      # clamp the block to the grid
    r2 = min(m-1, i + k); c2 = min(n-1, j + k)
    answer[i][j] = P[r2+1][c2+1] - P[r1][c2+1]   # big rectangle ...
                 - P[r2+1][c1] + P[r1][c1]        # ... minus strips, plus corner
return answer

The Python solution

def matrix_block_sum(mat, k):
    m, n = len(mat), len(mat[0])
    P = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m):
        for j in range(n):
            P[i + 1][j + 1] = mat[i][j] + P[i][j + 1] + P[i + 1][j] - P[i][j]
    ans = [[0] * n for _ in range(m)]
    for i in range(m):
        for j in range(n):
            r1, c1 = max(0, i - k), max(0, j - k)
            r2, c2 = min(m - 1, i + k), min(n - 1, j + k)
            ans[i][j] = (P[r2 + 1][c2 + 1] - P[r1][c2 + 1]
                         - P[r2 + 1][c1] + P[r1][c1])
    return ans

• P is one row and one column bigger than mat; that zero padding is what lets the corner formula index P[r1] and P[c1] safely when a block starts at the edge.
• The build loop uses inclusion-exclusion: cell + above + left - diagonal, because the above and left rectangles both already counted the diagonal overlap.
• r1, c1 = max(0, i - k), max(0, j - k) clamps the top-left of the block so it never goes negative.
• r2, c2 = min(m - 1, i + k), min(n - 1, j + k) clamps the bottom-right so it never runs past the last row/column.
• The four-corner read is the 2-D analog of prefix[hi] - prefix[lo]: one big rectangle, minus the strip above, minus the strip to the left, plus the corner that got subtracted twice.

Complexity

We trade O(m·n) extra space (the prefix table) to drop the time from O(m·n·k²) to O(m·n). The block size k disappears from the cost entirely — every query is four lookups no matter how big the window is.

When this pattern shows up

Practice