矩阵区域和 图解题解

answer[i][j] 到底把哪些格子加起来

给一个 m 行 n 列矩阵 mat 和整数 k，输出同样大小的 answer：每个 answer[i][j] 是以 (i,j) 为中心、边长 2k+1 的方块里所有数之和，探出矩阵的部分剪掉。题面 mat=[[1,2,3],[4,5,6],[7,8,9]]、k 取 1，answer[1][1] 盖满全矩阵、值 45。

逐格累加每个窗口，卡在哪

把每个 answer[i][j] 拆开逐格加，外两重循环走遍 m·n 个中心，里两重循环扫窗口最多 (2k+1)² 个格子，四重、O(m·n·k²)。k 一大，同一格被周围一圈中心反复加，全是白工。

二维前缀和：一次建表，每格四项算块和

先建二维前缀和表 s，让 s[i][j] 存原矩阵左上角到 (i-1,j-1) 这块矩形的总和。有了它，任意矩形区域的和拿四个角一加减就得出——大块减上条、减左条、再加回左上块，即四项容斥。区域求和从 O(k²) 降到 O(1)。

建表怎么递推、查块前先把窗口钳进矩阵

建表 s 开成 (m+1) 乘 (n+1)，最上一行最左一列全填 0 当哨兵。每个 s[i][j] = 上面一块 s[i-1][j] 加左边一块 s[i][j-1]，两块在左上小块 s[i-1][j-1] 上重叠、减一次，再补当前格的值。有了这圈零，第一行第一列的越界项天然取 0，不必单独判边界。

算 answer[i][j] 前先把窗口钳进矩阵：x1=max(i-k,0)、y1=max(j-k,0) 定左上角，x2=min(m-1,i+k)、y2=min(n-1,j+k) 定右下角。中心在角或边上时 i-k 变负、i+k 越末行，不钳就越界。查表带 +1 偏移：哨兵让下标右移一格，右下角查 s[x2+1][y2+1]、左上角查 s[x1][y1]，故下一节右下是 s[3]、左上是 s[0]。

拿题面矩阵把三个 answer 亲手算一遍

先填 s。哨兵那圈是 0，s[1][1]=0+0-0+1=1，s[1][2]=3、s[1][3]=6；第二行 s[2] 是 5、12、21；第三行 s[3] 是 12、27，s[3][3]=21+27-12+9=45，正是九个数总和。

算 answer[1][1]：窗口盖满矩阵，钳完行 0 到 2、列 0 到 2，s[3][3]-s[0][3]-s[3][0]+s[0][0]=45。算 answer[0][0]：窗口行 -1 到 1、列 -1 到 1 钳成行 0 到 1、列 0 到 1，s[2][2]-s[0][2]-s[2][0]+s[0][0]=12，正好是 1+2+4+5。

复杂度，还有两处最坑的偏移

两段扫描都线性：建表 O(m·n)、每格查表四次加减合起来 O(m·n)，比逐格累加的 O(m·n·k²) 快得多；前缀表 s 占 (m+1)×(n+1)、空间 O(m·n)。两处偏移最坑：前缀表若不多开那一圈零，第一行第一列就得单独写边界 if；四角的偏移正负号一记混，抠出的矩形整个错位。边界也好验：k 盖满全矩阵时每格是总和 45，k 为 0 时原样返回 mat。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:
        m, n = len(mat), len(mat[0])
        s = [[0] * (n + 1) for _ in range(m + 1)]
        for i, row in enumerate(mat, 1):
            for j, x in enumerate(row, 1):
                s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + x
        ans = [[0] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                x1, y1 = max(i - k, 0), max(j - k, 0)
                x2, y2 = min(m - 1, i + k), min(n - 1, j + k)
                ans[i][j] = (
                    s[x2 + 1][y2 + 1] - s[x1][y2 + 1] - s[x2 + 1][y1] + s[x1][y1]
                )
        return ans

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
        int m = mat.size();
        int n = mat[0].size();

        vector<vector<int>> s(m + 1, vector<int>(n + 1));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                s[i + 1][j + 1] = s[i][j + 1] + s[i + 1][j] - s[i][j] + mat[i][j];
            }
        }

        vector<vector<int>> ans(m, vector<int>(n));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                int x1 = max(i - k, 0);
                int y1 = max(j - k, 0);
                int x2 = min(m - 1, i + k);
                int y2 = min(n - 1, j + k);
                ans[i][j] = s[x2 + 1][y2 + 1] - s[x1][y2 + 1] - s[x2 + 1][y1] + s[x1][y1];
            }
        }
        return ans;
    }
};

Java

import java.util.*;
class Solution {
    public int[][] matrixBlockSum(int[][] mat, int k) {
        int m = mat.length;
        int n = mat[0].length;
        int[][] s = new int[m + 1][n + 1];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                s[i + 1][j + 1] = s[i][j + 1] + s[i + 1][j] - s[i][j] + mat[i][j];
            }
        }

        int[][] ans = new int[m][n];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                int x1 = Math.max(i - k, 0);
                int y1 = Math.max(j - k, 0);
                int x2 = Math.min(m - 1, i + k);
                int y2 = Math.min(n - 1, j + k);
                ans[i][j] = s[x2 + 1][y2 + 1] - s[x1][y2 + 1] - s[x2 + 1][y1] + s[x1][y1];
            }
        }
        return ans;
    }
}