第 9 章：前缀和与差分 (Prefix Sum & Difference Array)

这两个算法互为逆运算：

前缀和：主要用于快速查询区间和。
差分：主要用于快速修改区间值。

9.1 一维前缀和： $O(1)$ 求区间和

假设原数组是 $A$ 。我们定义前缀和数组 $S$ ，其中 $S[i]$ 表示前 $i$ 个数的总和。 $S[i] = A[1] + A[2] + \dots + A[i]$

9.1.1 递推公式

$S[i] = S[i-1] + A[i]$ (注意：为了方便计算，我们通常让数组下标从 1 开始，令 $S[0] = 0$ )

9.1.2 核心魔法

如何求 $A[l]$ 到 $A[r]$ 的和？想一想： $S[r]$ 是前 $r$ 个数的和， $S[l-1]$ 是前 $l-1$ 个数的和。两者相减，剩下的就是第 $l$ 到第 $r$ 个数。

公式： $\text{Sum}(l, r) = S[r] - S[l-1]$

代码模板

#include <iostream>
#include <vector>
using namespace std;
 
int main() {
    int n, m; // n个数，m次询问
    cin >> n >> m;
    
    // 使用 vector，大小设为 n+1，下标从 1 开始
    vector<long long> s(n + 1, 0); 
    
    for (int i = 1; i <= n; i++) {
        int x; cin >> x;
        // 读入的同时直接计算前缀和
        s[i] = s[i - 1] + x;
    }
    
    while (m--) {
        int l, r;
        cin >> l >> r;
        // O(1) 回答询问
        cout << s[r] - s[l - 1] << endl;
    }
    return 0;
}

9.2 二维前缀和：矩阵求和

场景：给你一个二维矩阵，问你坐标 $(x_1, y_1)$ 到 $(x_2, y_2)$ 围成的子矩形内所有数字的和是多少？

如果我们把一维的思想扩展到二维， $S[i][j]$ 表示从 $(1,1)$ 到 $(i,j)$ 这个矩形内所有元素的和。

9.2.1 构造公式 (容斥原理)

想象一下图形： $S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + A[i][j]$ 解释：

加上上面的面积 $S[i-1][j]$
加上左边的面积 $S[i][j-1]$
减去重复加的左上角面积 $S[i-1][j-1]$
最后加上当前格子 $A[i][j]$

9.2.2 查询公式

要求 $(x_1, y_1)$ 到 $(x_2, y_2)$ 的子矩阵和： $\text{Sum} = S[x_2][y_2] - S[x_1-1][y_2] - S[x_2][y_1-1] + S[x_1-1][y_1-1]$ 解释：也就是“大矩形”减去“上面多余的”和“左边多余的”，最后把“左上角多减了一次的部分”加回来。

9.3 一维差分： $O(1)$ 区间修改

场景：给你一个全为 0 的数组，做 $M$ 次操作，每次把区间 $[l, r]$ 内的所有数都加上 $V$ 。最后输出这个数组。如果用循环暴力加，是 $O(MN)$ 。用差分数组，是 $O(M)$ 。

9.3.1 定义

差分是前缀和的逆运算。构造一个数组 $D$ ，使得 $A[i]$ 是 $D$ 的前缀和。 $D[i] = A[i] - A[i-1]$

9.3.2 核心操作

如果我们想让 $A$ 数组中 $l$ 到 $r$ 的每个数都加上 $V$ ，只需要操作 $D$ 数组的两个点：

$D[l] += V$
- 这意味着从 $l$ 开始，所有原本的 $A$ 值（前缀和）都会增加 $V$ 。
$D[r+1] -= V$
- 这意味着从 $r+1$ 开始，把刚才增加的 $V$ 抵消掉。

代码实现

// 假设 n = 10，我们做若干次修改
vector<int> d(20, 0); // 差分数组
 
void add(int l, int r, int v) {
    d[l] += v;
    d[r + 1] -= v;
}
 
int main() {
    // 操作：[2, 5] 加上 3
    add(2, 5, 3);
    // 操作：[4, 8] 减去 2
    add(4, 8, -2);
    
    // 最后还原成原数组 A（做一次前缀和）
    vector<int> a(20);
    for (int i = 1; i <= 10; i++) {
        a[i] = a[i - 1] + d[i]; // 当前值 = 前一个值 + 差分值
        cout << a[i] << " ";
    }
}

9.4 进阶：二维差分

场景：把 $(x_1, y_1)$ 到 $(x_2, y_2)$ 这个子矩阵内的所有数都加上 $V$ 。

不需要死记硬背，类比一维差分：

$D[x_1][y_1] += V$ (让右下角所有区域都加上 $V$ )
$D[x_1][y_2+1] -= V$ (把右边多加的砍掉)
$D[x_2+1][y_1] -= V$ (把下面多加的砍掉)
$D[x_2+1][y_2+1] += V$ (因为刚才砍了两次，重叠区域多砍了一次，要补回来)

最后对 $D$ 数组求一遍二维前缀和，就得到了修改后的原矩阵。

🧠 本章小结与练习

前缀和与差分是处理静态数组（Static Array）区间操作的神器。

如果你需要多次询问，但数组不怎么修改 $\to$ 前缀和。
如果你需要多次修改，但只在最后询问一次 $\to$ 差分。

⚠️ 思考：如果你既要频繁修改，又要频繁询问，怎么办？这时候前缀和就不够用了（修改一次前缀和数组需要 $O(N)$ ）。我们需要更高级的数据结构——线段树 (Segment Tree) 或 树状数组 (BIT)（这是后续的高级章节内容）。

练习作业：

P8218 【深进1.例1】求区间和 (洛谷)：一维前缀和模板题。
P1719 最大加权矩形：二维前缀和的应用，配合 $O(N^4) \to O(N^3)$ 的优化。
P2367 语文成绩：差分数组模板题，经典的“区间加分”问题。

掌握了数组的处理技巧，接下来我们要处理一种稍微复杂一点的关系——“集合”。怎么快速判断两个元素是不是朋友？怎么把两个帮派合并成一个？