矩阵块和怎么用二维前缀和快速计算？

简化版

矩阵块和要求每个位置周围 k 范围内的子矩阵和。

先构建二维前缀和，然后对每个位置 (i, j)，把块边界裁剪到矩阵范围内。

用二维前缀和公式 O(1) 求出该子矩阵和，整体复杂度 O(mn)。

详细版

对每个单元格 (i, j)，目标区域是：

[i-k, i+k] x [j-k, j+k]

但边界可能越界，所以要裁剪：

r1 = max(0, i-k)
c1 = max(0, j-k)
r2 = min(m-1, i+k)
c2 = min(n-1, j+k)

二维前缀和 prefix 使用多一行多一列的定义。查询子矩阵时：

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

这样每个格子的块和都能常数时间计算。

完整版教学

一、为什么暴力会重复计算

如果对每个格子都重新遍历它周围的块，块大小最多约为 (2k+1)^2。当矩阵是 1000 x 1000、k = 50 时，每个格子可能扫 10201 个元素，总操作量非常大。二维前缀和把任意子矩阵求和变成 4 个角的加减，避免重复遍历。

记忆钩子：矩阵里“每个点都问一个矩形和”，优先想二维前缀和。

二、二维前缀和的定义

定义 P 大小为 (m+1) x (n+1)，P[i+1][j+1] 表示原矩阵从 (0,0) 到 (i,j) 的矩形和。多出来的一行一列用于处理贴边矩形，避免大量边界判断。

位置	含义
`P[0][*]`	空上边界
`P[*][0]`	空左边界
`P[i+1][j+1]`	包含原矩阵 `(i,j)` 的左上矩形

构建时使用容斥公式。

三、构建公式为什么要减交集

计算 P[i+1][j+1] 时，上方矩形和左方矩形都包含了左上公共区域，所以要减掉一次，再加当前格子。

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

这和集合容斥一样：上方 + 左方 - 重复交集 + 当前点。

四、查询公式怎么来

查询 (r1,c1) 到 (r2,c2) 的子矩阵：

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

先取从原点到右下角的大矩形，再减掉上方和左方多余部分。左上角被减了两次，所以加回来一次。

五、代码模板

实现如下：

function matrixBlockSum(mat, k) {
  const m = mat.length
  const n = mat[0].length
  const p = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0))
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      p[i + 1][j + 1] = p[i][j + 1] + p[i + 1][j] - p[i][j] + mat[i][j]
    }
  }
  const query = (r1, c1, r2, c2) =>
    p[r2 + 1][c2 + 1] - p[r1][c2 + 1] - p[r2 + 1][c1] + p[r1][c1]

  const ans = Array.from({ length: m }, () => Array(n).fill(0))
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      const r1 = Math.max(0, i - k)
      const c1 = Math.max(0, j - k)
      const r2 = Math.min(m - 1, i + k)
      const c2 = Math.min(n - 1, j + k)
      ans[i][j] = query(r1, c1, r2, c2)
    }
  }
  return ans
}

边界裁剪和前缀查询是这题的两个核心步骤。

六、常见误区与追问

误区：每个格子重新暴力求块和。 会产生大量重复计算，复杂度偏高。
误区：二维前缀和少开一行一列。 边界查询会变得难写，容易越界。
误区：查询公式忘记加回左上交集。 容斥少一步会导致结果偏小。
追问：k 很大怎么办？ 边界裁剪后区域最多就是整个矩阵，公式仍然成立。
追问：矩阵会更新怎么办？ 普通二维前缀和不适合频繁更新，应考虑二维树状数组或线段树。

这些追问考的是二维容斥是否真的理解。

七、加强记忆

矩阵块和记成“先造二维前缀，再裁边界，最后四角容斥”。P 多开一行一列让边界统一；每个 (i,j) 的块范围用 max/min 裁到合法矩阵内；查询时用右下大矩形减上减左加交集。这样每个格子都是 O(1) 查询。

简化版

详细版