前缀和与差分：让你轻松搞定区间操作的好搭档

你有没有遇到过这样的问题——老师要给班里某一段学号的同学每人加5分，然后又给另一段同学加3分，最后你想快速算出某个同学的总加分？或者，你在玩一个“埋地雷”游戏，地图上每个格子初始是0，你一次次地在不同矩形区域埋雷（每个格子被埋一次就加1），最后想知道每个格子被埋了几次？

如果用最笨的方法——每次真的去改每个格子，当格子很多、操作很多时，计算机就会跑得越来越慢，甚至会超时。这时候，前缀和和差分这对好兄弟就能帮你大忙了。它们一个擅长快速算出某段区间的和，一个擅长快速给一段区间统一加减。把这两个技巧结合起来，就能像变魔术一样，用很少的计算量解决看起来复杂的问题。

先复习一下：前缀和——快速求区间和

假设你有一个数组 a，你想知道从第 l 个位置到第 r 个位置的和。如果每次都把 l 到 r 的数加一遍，当数组很大、查询很多时，就太慢了。前缀和就是提前算好一个“累积和”数组 pre，其中 pre[i] 表示原数组前 i 个数的和。这样，a[l] 到 a[r] 的和就等于 pre[r] - pre[l-1]，一次减法就搞定。

生活小例子：你每天的零花钱记录如下：第1天5元，第2天10元，第3天20元，第4天15元。你想知道第2天到第4天一共花了多少？把每天的钱存进数组，算出前缀和 pre：pre[1]=5, pre[2]=15, pre[3]=35, pre[4]=50。那么第2到第4天的和 = pre[4]-pre[1] = 50-5 = 45，这和你直接加 10+20+15 的结果一样，但快得多。

再复习一下：差分——快速区间统一加减

差分是前缀和的“逆运算”。假如你有一个全是0的数组 a，现在你想让区间 [l, r] 内的每个数都加上 x。常规做法是用循环一个个加，但用差分数组 diff 只需要两步操作：diff[l] += x 和 diff[r+1] -= x。所有操作完成后，对 diff 数组求一次前缀和，就能得到 a 每个位置的最终值。

为什么这样可行？因为差分数组记录了每个位置的变化“增量”。把 diff 从左往右累加，就能还原出每个位置实际被加了多少次。

生活小例子：班里10个同学，初始分数都是0。老师给第3到第7名同学每人加5分，然后又给第1到第4名同学每人加3分。用差分数组 diff（大小11，下标从1开始）：

• 第一次操作：diff[3] += 5, diff[8] -= 5
• 第二次操作：diff[1] += 3, diff[5] -= 3 操作完后，对 diff 求前缀和。比如第3个同学：累加时得到 diff[1]+diff[2]+diff[3] = 3+0+5=8，正确。第5个同学：累加 diff[1]~diff[5] = 3+0+5+0-3=5，也正确。根本不需要每次真的去循环修改每个同学。

经典组合：先做m次区间修改，再求每个位置的最终值

现在我们回到文章开头的问题：一条街上 n 个路灯，一开始全关（值为0）。小明做了 m 次操作，每次把第 l 到第 r 个路灯的亮度提高1（比如开关一次）。最后，他想知道每个路灯被操作了多少次。

用差分数组 diff（大小至少 n+2，因为要用到 r+1），每次操作：

diff[l] += 1;   // 从 l 开始加一次
diff[r+1] -= 1; // 到 r+1 就停止加

所有操作完成后，对 diff 做一次前缀和，就能得到每个路灯的最终操作次数。

完整可运行的C++代码

下面是一个你可以直接复制到电脑上运行的完整程序。它模拟了路灯的例子，让你亲手试试效果。

#include <iostream>
using namespace std;

int main() {
    int n, m;
    cout << "请输入路灯个数( n )和操作次数( m )：";
    cin >> n >> m;

    // 差分数组，下标从1到n+1，防止越界
    int diff[1005] = {0};  // 假设n<=1000，预留大一点

    cout << "请依次输入每次操作的 l 和 r（用空格隔开）：" << endl;
    for (int i = 1; i <= m; i++) {
        int l, r;
        cin >> l >> r;
        // 在 l 处加 1，在 r+1 处减 1
        diff[l] += 1;
        diff[r + 1] -= 1;
    }

    // 用前缀和还原出每个路灯的实际操作次数
    int ans[1005] = {0};
    cout << "每个路灯被操作的次数：";
    for (int i = 1; i <= n; i++) {
        ans[i] = ans[i - 1] + diff[i];
        cout << ans[i] << " ";
    }
    cout << endl;

    return 0;
}

试试这个例子：
输入 n=5, m=2，然后输入 1 3 和 2 4。程序输出应该是 1 2 2 1 0。
解释：第一次操作加在第13个路灯，第二次加在第24个路灯。每个路灯被操作的次数：

• 第1个：只有第一次 → 1次
• 第2个：两次都有 → 2次
• 第3个：两次都有 → 2次
• 第4个：只有第二次 → 1次
• 第5个：没有 → 0次
  结果完全正确！

新手容易犯的错误

1. 差分数组大小不够
   因为我们要访问 diff[r+1]，如果 r 等于 n，那么 r+1 就是 n+1。所以数组大小至少是 n+2。很多同学只开了 n+1，结果越界出错。

2. 下标从0还是从1开始
   通常为了和生活中编号从1开始一致，我们让数组下标从1开始。如果题目给的下标是从0开始的，要小心转换。比如题目说第0个到第5个，那么 l=0, r=5，差分操作变成 diff[0] += x; diff[r+1] -= x，但 diff 的索引还是0~n-1，需要把 r+1 考虑清楚。建议统一用1-based，方便理解。

3. 忘记在最后求前缀和
   有的人只做了差分修改，直接输出 diff 数组，以为那就是答案。错了！diff 存的是“变化量”，必须经过一次前缀和还原才能得到真实值。

4. 多次查询穿插修改
   差分+前缀和只适用于“先全部修改，最后统一查询”的场景。如果修改和查询交替进行（比如改一次、查一次、再改一次），那么每次修改后都需要重新做前缀和，这样反而变慢了。这种情况需要用更高级的数据结构，比如树状数组或线段树。

更多拓展：二维的妙用

很多人觉得一维玩够了，但生活中很多问题是两维的，比如一张地图、一张表格、一张图片。前缀和和差分都有二维版本。

二维前缀和

用于快速求二维表格中任意矩形区域的和。比如一张 n×m 的图片，每个格子有一个亮度值，你想知道从 (x1,y1) 到 (x2,y2) 的矩形内所有格子的亮度总和。用二维前缀和 pre[i][j] 表示从 (1,1) 到 (i,j) 矩形的和，那么目标矩形的和 = pre[x2][y2] - pre[x1-1][y2] - pre[x2][y1-1] + pre[x1-1][y1-1]。这个公式就像拼图一样，通过加减四个矩形得到。

二维差分

用于给二维数组的某个矩形区域统一加减。比如你想在一张地图上挖一个矩形区域作为“雷区”，让所有格子值加1。用二维差分 diff 数组，只需要修改四个角：
diff[x1][y1] += 1;
diff[x1][y2+1] -= 1;
diff[x2+1][y1] -= 1;
diff[x2+1][y2+1] += 1;
然后对整个 diff 做两次一维前缀和（先按行累加，再按列累加，或者反过来），就能得到每个格子最终的值。

生活例子：你有一张10×10的果园地图，初始每棵树结果0个。小明在矩形 (2,3)~(5,7) 里每棵树上挂了1个果子，又在矩形 (4,2)~(8,6) 里每棵树上挂了2个果子。最后你想知道每棵树上有几个果子。用二维差分做两次修改，最后前缀和还原，非常快。

当修改和查询交替出现时怎么办？

虽然前缀和+差分组合可以在一次前缀和后支持多次查询（因为前缀和数组建好后，任意的区间和都可以O(1)得到），但如果修改和查询是穿插的，这种方法就不行了。例如：改一次、查一次、再改一次、再查一次……每次修改都要重新建前缀和，太慢。此时就需要树状数组或线段树来支援了。它们可以在O(log n)时间内完成单点修改或区间查询，是解决动态问题的利器。不过，对于静态问题（所有修改在前，所有查询在后），差分+前缀和仍然是最简单最快速的方法。

小总结

前缀和和差分就像一对形影不离的好朋友：前缀和能快速回答“一段区间之和”，差分能快速实现“一段区间统一加减”。把它们结合起来，你就能轻松处理“先做一堆修改，再问一堆结果”的问题。写代码时注意边界和数组大小，就能避开常见的陷阱。

如果你已经掌握了这些基本技巧，下一步可以挑战一下：

• 二维前缀和与二维差分（上面提到过）
• 树状数组（支持动态修改和查询）
• 线段树（更强大的区间操作神器）

记住，遇到“多次区间修改 + 多次区间查询”的题目时，先问问自己：修改和查询的顺序是怎样的？如果修改都在前面，查询都在后面，那就毫不犹豫地用差分+前缀和吧！你的程序会像闪电一样快。