[算法学习]模板-二维前缀和与二维差分

二维前缀和与二维差分，是一维版本的自然扩展。本质仍然是：

前缀和 → 解决查询
差分   → 解决修改

二维只是把一维的“区间”扩展为“子矩阵”。

---

一、二维前缀和（2D Prefix Sum）

---

一、问题背景

给定一个 n × m 的矩阵 a，需要多次查询：

子矩阵 (x1, y1) 到 (x2, y2) 的元素总和。

如果每次查询都暴力枚举：

O(nm) 每次

多次查询会直接超时。

二维前缀和的目标是：

预处理 O(nm)
单次查询 O(1)

---

二、定义

定义二维前缀和数组：

s[i][j]

表示：

从 (1,1) 到 (i,j) 这个矩形区域内的所有元素之和

---

三、递推公式推导（核心）

考虑构造 s[i][j]：

s[i][j] =
    上方区域
  + 左侧区域
  - 重叠区域
  + 当前元素

数学表达式：

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

为什么要减去 s[i-1][j-1]？

因为：

s[i-1][j] 和 s[i][j-1]

都包含了左上角区域 (1,1)~(i-1,j-1)，被加了两次，所以必须减去一次。

这就是二维前缀和的“容斥思想”。

---

四、子矩阵查询公式

查询：

(x1, y1) ~ (x2, y2)

公式：

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

本质仍然是容斥。

---

五、标准竞赛模板（cin/cout 版）

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 1010;

ll a[N][N];
ll s[N][N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, q;
    cin >> n >> m >> q;

    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            cin >> a[i][j];
            s[i][j] = a[i][j]
                    + s[i - 1][j]
                    + s[i][j - 1]
                    - s[i - 1][j - 1];
        }
    }

    while(q--)
    {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;

        cout << s[x2][y2]
             - s[x1 - 1][y2]
             - s[x2][y1 - 1]
             + s[x1 - 1][y1 - 1]
             << '\n';
    }

    return 0;
}

---

六、注意事项（高频踩坑）

1️⃣ 必须 1-based

原因：

需要用到 s[0][*] 和 s[*][0]

默认全局数组初始化为 0，可以直接使用。

如果你用 0-based，会非常容易写错容斥。

---

2️⃣ 容斥符号不要写错

记忆顺序：

+ 右下
- 上
- 左
+ 左上

---

3️⃣ 使用 long long

如果：

n,m ≤ 1000
a[i][j] ≤ 1e9

最大和可能达到：

1e9 × 1e6 = 1e15

必须用 long long。

---

4️⃣ 空间大小

如果题目最大是 1000：

const int N = 1005 或 1010

不要开太小。

---

七、时间复杂度

阶段	复杂度
预处理	O(nm)
单次查询	O(1)
总计	O(nm + q)

---

二、二维差分（2D Difference Array）

---

一、问题背景

现在问题变成：

多次对矩形 (x1,y1)~(x2,y2) 内所有元素加 d

暴力修改：

O(nm) 每次

二维差分可以做到：

O(1) 每次修改

---

二、二维差分定义

差分是二维前缀和的逆操作。

定义：

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

还原方式：

对 b 做二维前缀和

即可得到最终数组。

---

三、矩形加法的四角标记

对矩形 (x1,y1)~(x2,y2) 加 d：

b[x1][y1]       += d
b[x2+1][y1]     -= d
b[x1][y2+1]     -= d
b[x2+1][y2+1]   += d

结构是：

+  - 
-  +

和二维容斥完全一致。

---

四、推导过程

在一维差分中，我们已经知道：

如果希望对区间 [l, r] 内所有元素加上 d，
只需在差分数组中进行两次操作：

b[l] += d
b[r+1] -= d

这是因为一维前缀和在还原时，会把当前位置之前的所有影响累加到当前点。
因此，一个差分数组中的单点修改，会向右侧扩散影响。

二维差分的思想与此完全一致。
只不过：

• 一维前缀和的影响是“向右扩散”
• 二维前缀和的影响是“向右下扩散”

也就是说，如果在差分数组 b[x][y] 处加上 d，
那么在还原时，所有满足 i ≥ x 且 j ≥ y 的位置都会受到影响。

因此，一个单点修改会影响右下角整块区域。

而我们的目标是：

只让矩形 (x1,y1) ~ (x2,y2) 受到影响，
其它区域不受影响。

那么问题就转化为：

如何把一个“向右下无限扩散”的影响，
精确地裁剪成一个有限的矩形？

在一维差分中，我们通过在区间右端点之后减去 d，
来阻断影响向右继续扩散。

在二维中，道理完全相同。

如果我们只执行：

b[x1][y1] += d;

那么影响会扩散到整个右下区域。

为了让影响在 x2 这一行停止继续向下扩散，
我们需要在 (x2+1, y1) 处减去 d：

b[x2+1][y1] -= d;

同理，为了让影响在 y2 这一列停止向右扩散，
我们需要在 (x1, y2+1) 处减去 d：

b[x1][y2+1] -= d;

但这样做之后，右下角区域被减去了两次，
因此需要在 (x2+1, y2+1) 处补回一次：

b[x2+1][y2+1] += d;

最终就得到四角修改结构：

b[x1][y1]       += d;
b[x2+1][y1]     -= d;
b[x1][y2+1]     -= d;
b[x2+1][y2+1]   += d;

其符号结构为：

+   -
-   +

这正是二维前缀和“容斥结构”的直接体现。

修改后需要还原到原数组进行输出，我们用数组c来接收修改后恢复成的原数组。

由于：差分数组求前缀和后是原数组。

我们把二维前缀和公式（prefix[x] [y]=prefix[x] [y-1]+prefix[x-1] [y] -prefix[x-1] [y-1]+a[x] [y]）这里a为原数组，prefix为原数组进行前缀和操作后的前缀和数组。

套用至此句话，则有

c[x] [y] = c[x] [y-1]+c[x-1] [y]-c[x-1] [y-1]+b[x] [y]

这里b为差分数组，c为差分数组进行前缀和操作后的修改后的原数组。

那么问题来了，我们该如何构建最初设想的这个差分数组呢，其实依据这个恢复公式就可以实现，我们对其逆向移项处理，这里的c[x] [y] 即被替换为最初的原数组a[x] [y]，则有b[x] [y] = a[x] [y] - a[x] [y-1] - a[x-1] [y] + a[x-1] [y-1] 这就是最初的构建差分数组公式。

我们顺着理下来，对矩阵元素进行区间修改的正确步骤即为：

1.依据原数组a构建差分数组b

2.对差分数组b进行操作进行区间修改

3.对进行过区间修改的差分数组b进行恢复操作得到c数组

c数组即所求的矩阵进行修改操作后的元素数组。

五、标准竞赛模板

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

// 适用于 n,m <= 1000，并且会访问到 x2+1、y2+1，所以要预留边界
const int N = 1010;

// a：原矩阵（输入）
// b：二维差分矩阵（用于打标记）
// c：最终恢复后的矩阵（输出）
ll a[N][N];
ll b[N][N];
ll c[N][N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, q;
    cin >> n >> m >> q;

    // 1) 读入原矩阵 a（1-based）
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            cin >> a[i][j];

    // 2) 由 a 构造二维差分 b
    //    b[i][j] = a[i][j] - a[i-1][j] - a[i][j-1] + a[i-1][j-1]
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            b[i][j] = a[i][j]
                    - a[i - 1][j]
                    - a[i][j - 1]
                    + a[i - 1][j - 1];
        }
    }

    // 3) 多次对子矩形 (x1,y1)~(x2,y2) 加 d
    //    在差分 b 上做四角标记（+ - - +）
    while(q--)
    {
        int x1, y1, x2, y2;
        ll d;
        cin >> x1 >> y1 >> x2 >> y2 >> d;

        b[x1][y1]         += d;
        b[x2 + 1][y1]     -= d;
        b[x1][y2 + 1]     -= d;
        b[x2 + 1][y2 + 1] += d;
    }

    // 4) 由差分 b 还原最终矩阵 c
    //    对 b 做二维前缀和，但“前缀化后的值”我们存入 c，保证三个数组职责清晰
    //
    //    c[i][j] = b[i][j] + c[i-1][j] + c[i][j-1] - c[i-1][j-1]
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            c[i][j] = b[i][j]
                    + c[i - 1][j]
                    + c[i][j - 1]
                    - c[i - 1][j - 1];
        }
    }

    // 5) 输出最终矩阵 c
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            cout << c[i][j] << (j == m ? '\n' : ' ');
        }
    }

    return 0;
}

---

五、二维差分注意事项

1️⃣ 必须预留 x2+1 和 y2+1

数组至少开到：

N >= n+2

否则越界。

---

2️⃣ 四角符号不能错

记忆结构：

+  -
-  +

---

3️⃣ 最后必须做二维前缀还原

否则输出的是差分数组，而不是最终矩阵。

---

六、时间复杂度

阶段	复杂度
构造差分	O(nm)
单次修改	O(1)
还原矩阵	O(nm)
总计	O(nm + q)

---

七、整体对比总结

类型	解决问题	本质
二维前缀和	子矩阵查询	容斥
二维差分	子矩阵修改	前缀和的逆

口诀：

查询用前缀和
修改用差分
二维是容斥的推广

---

这两个模板是：

• 二维树状数组
• 二维线段树
• 二维扫描线

的前置知识。