auto_ai 知识库

Appearance

二维前缀和是一种预处理技术，通过构建前缀和矩阵实现 O(1) 时间内查询任意子矩阵的元素和。核心是利用容斥原理避免重复计算，适用于大量子矩阵求和查询的场景。

定义与核心原理 ​

设原矩阵为 a[i][j]，前缀和矩阵为 s[i][j]，表示从左上角 (1,1) 到 (i,j) 的矩形区域内所有元素之和。

构建公式（容斥原理） ​

s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j]

图解：

(1,1)到(i,j)的和 = (1,1)到(i-1,j)的和   [上方矩形]
                 + (1,1)到(i,j-1)的和   [左方矩形]
                 - (1,1)到(i-1,j-1)的和 [重叠部分，被加了两次]
                 + a[i][j]              [当前元素]

查询公式（容斥图解） ​

求以 (x1,y1) 为左上角、(x2,y2) 为右下角的子矩阵和：

sum = s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]

图解四步拆解：

目标子矩阵 (x1,y1)~(x2,y2)
= 大矩形 (1,1)~(x2,y2)
- 上方矩形 (1,1)~(x1-1,y2)      [减去顶部多余部分]
- 左方矩形 (1,1)~(x2,y1-1)      [减去左侧多余部分]
+ 重叠矩形 (1,1)~(x1-1,y1-1)    [加回被减了两次的重叠部分]

关键：(x1-1,y1-1) 这块区域被上方矩形和左方矩形各减了一次，共减两次，所以要加回来一次。

操作步骤 ​

1. 构建前缀和矩阵 ​

cpp
// 下标从 1 开始，避免边界判断
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j];
    }
}

2. 查询子矩阵和 ​

cpp
int query(int x1, int y1, int x2, int y2) {
    return s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1];
}

复杂度分析 ​

操作时间复杂度说明
预处理O(n×m)构建前缀和矩阵
单次查询O(1)直接公式计算
空间O(n×m)前缀和矩阵

实践应用 ​

  • 矩阵区域求和：多次查询子矩阵元素和
  • 图像积分图：计算机视觉中快速计算矩形区域像素和
  • 二维差分的逆运算：与二维差分配合解决区间修改问题
  • 最大子矩阵和：枚举上下边界，一维前缀和求最大子数组

常见误区 ​

  1. 下标从 0 开始：建议从 1 开始，否则 s[i-1][j] 会越界，需要额外判断
  2. 容斥符号记错：构建和查询都是"加两个、减一个"，不要搞反
  3. 数据溢出：矩阵元素和可能超过 int 范围，用 long long

一句话总结 ​

二维前缀和靠容斥原理预处理 O(n×m)，之后任意子矩阵求和都是 O(1)；构建和查询都记"加两个、减一个"，下标从 1 开始可免边界判断。

相关概念 ​