CC++ & Algorithm

差分**

困难1
语言版本：C++
概述：差分是前缀和的“反向操作”，就像给一段线段的每个点都加同样的高度，只需要在线段两端做个标记。**

巧用差分数组，轻松搞定多次区间加法

想象一下，你有一排10个存钱罐（编号1到10），每个存钱罐里一开始都是空的。现在妈妈要给你连续几个存钱罐里各放1块钱，比如第3到第7个。如果你一个罐子一个罐子地放，要放5次。如果后面还有100次这样的操作，每次都是给不同连续的一排罐子放钱，那你就得跑上千次，累坏了。

差分就是帮你“偷懒”的聪明办法：每次只需要在开始的那个罐子和结束的下一个罐子做个标记，最后再统一把标记“传递”下去，一次就搞定全部。就像在生活中，家长想给连续几天的零花钱加1元，只在第一天写个“+1”，在结束日的后一天写个“-1”，最后每天结算的时候看看“累计标记”就知道今天该加多少。

在编程中，差分算法专门用来高效处理 “多次对数组中一段连续区间加同一个数” 的问题。它把每次修改的时间从 O(n) 降到了 O(1)，做完所有操作后再用一次 O(n) 的“前缀和”计算最终结果。

一、差分是什么——先做标记，最后统一结算

假设你有一个初始数组 arr（长度 n），你想把区间 [L, R] 里的每个数都加上 val。

普通做法：用循环从 L 到 R 依次加 val。一次操作的时间是 O(R-L+1)，如果有 m 次操作，总时间就是 O(m * n) 级别。

差分做法：创建一个辅助数组 diff（长度 n+2，多两个位置防越界），初始全为 0。每次操作只需要两步：

diff[L] += val        # 从位置 L 开始，后面的每个数都会多加 val
diff[R+1] -= val      # 到位置 R+1 时，把多加的 val 减回去，保证 R 之后不受影响

等所有操作都做完后，对 diff 数组求前缀和（从左到右累加），就能得到每个位置实际增加的总量，再与原始的 arr 相加，就是最终结果。

为什么这么神奇？因为 diff[i] 记录了“在位置 i 开始的累积增量变化”。你可以在脑中模拟：从第一个位置开始走，每走一步，手上拿着一个“当前应加的数值”，遇到 diff[i] 是正数就增加手里的值，是负数就减少。这样走到哪里，手里的值就是当前位置应该加的增量。

二、打个比方——用身高来理解

假设有10个同学站成一排（位置1~10），大家身高一开始都是0。现在要给他们长个子：第3到第7个同学每人长高1厘米。普通方法是老师拿尺子挨个量、挨个标记。差分方法呢？

老师拿一块牌子，上面写“+1”，插在位置3前面；再拿一块牌子写“-1”，插在位置8前面（因为第7个之后的下一个就是8）。然后老师对大家说：“从位置3开始，每往后一个人，就把牌子的数字加到你身上，直到看见‘-1’的牌子就停止加这个1。”这样，位置1、2没看到牌子，不变；位置3看到“+1”，身高+1；位置4、5、6、7也持续看到+1（因为没遇到-1），身高+1；位置8看到“-1”，身高不再增加，后面位置9、10也都没增加。完美！

三、具体操作步骤（含生活例子）

例子：零花钱每天上涨

小明每天有零花钱，记录在 money 数组里（下标从1开始）。爸爸决定在 第3天到第7天 每天多给1元，又在 第5天到第9天 每天多给2元。爸爸不想每天改记录，就用差分：

  1. 初始化 diff 长度为 n+2（多两个位置防止 R+1 越界），全0。
  2. 第一次操作 [3,7] 加1：diff[3] += 1，diff[8] -= 1。
  3. 第二次操作 [5,9] 加2：diff[5] += 2，diff[10] -= 2。
  4. 所有操作做完后，计算 diff 的前缀和得到每个位置的总增量，加到原数组上。

代码演示（保留原有示例并详细注释）

n = 10                                    # 数组长度
arr = [0] * (n + 2)                       # 原始零花钱，下标1~10，多两个位置防越界
diff = [0] * (n + 2)                      # 差分数组，同样多两个位置

# 操作1：第3天到第7天每天加1元
L1, R1, val1 = 3, 7, 1
diff[L1] += val1                          # 从L1开始，累积增量+1
diff[R1 + 1] -= val1                      # 在R1+1处，累积增量-1

# 操作2：第5天到第9天每天加2元
L2, R2, val2 = 5, 9, 2
diff[L2] += val2                          # 从L2开始，累积增量+2
diff[R2 + 1] -= val2                      # 在R2+1处，累积增量-2

# 最后用前缀和还原：遍历每个位置，累加diff得到实际增量
now = 0                                   # 当前累积增量
for i in range(1, n + 1):
    now += diff[i]                        # 加上当前位置的变化量
    arr[i] = now                          # 本题原始arr全0，所以arr[i]就是增量本身

print("最终零花钱（每天增量）：", arr[1:n+1])  # 输出： [0, 0, 1, 1, 3, 3, 3, 2, 2, 0]

解释输出：

  • 第1、2天：0
  • 第3、4天：只有操作1（加1）影响，所以是1
  • 第5~7天：两个操作叠加（加1+加2=3）
  • 第8、9天：操作2影响（加2），操作1已结束
  • 第10天：无影响

四、为什么高效？——对比朴素方法

方法一次操作的时间m次操作 + 最后还原适用场景
朴素循环O(n)O(m * n)操作次数少，数组小
差分O(1)O(m + n)操作次数多，数组大

当 m 和 n 都很大时，差分优势明显。比如 n=10万，m=10万，朴素法需要 100亿次操作，差分只需 20万次（10万次标记+10万次前缀和）。

五、新手容易犯的错误

  1. 忘记处理 R+1 越界
    如果 R 是最后一个位置（比如 n=10，R=10），那么 R+1=11，如果不将数组长度设为 n+2，会造成索引越界。所以习惯用 arr = [0] * (n + 2) 多留两个位置。

  2. 数组从0开始还是从1开始混淆
    多数差分题目喜欢用下标从1开始，方便理解。如果从0开始，则需要小心处理，但原理一样。建议统一从1开始，把0号位置空出来。

  3. 操作顺序搞反
    一定是 diff[L] += val 和 diff[R+1] -= val，不能写成 diff[L] -= val（除非你要减）。

  4. 以为可以同时做区间赋值
    差分只能做“区间加同一个数”，不能做“区间赋值成同一个数”。如果要把区间变成固定值，需要用线段树或差分+前缀和的变种（比如二维差分可以处理矩形区域，但也不是赋值）。

  5. 多次操作后未重置 diff
    每次新的问题需要新建一个 diff 数组，或者在原数组上多次使用时要先清零。

六、完整可运行示例（模拟游戏怪物加血）

假设游戏中有10个怪物（编号110），初始血量都是0。玩家施放两个群体技能：第一个技能对第37号怪物造成1点伤害（加负数）；第二个技能对第5~9号怪物治疗2点（加正数）。用差分一次处理：

n = 10                                       # 怪物数量
blood = [0] * (n + 2)                        # 初始血量，多两个位置防越界
diff = [0] * (n + 2)                         # 差分数组

# 技能1：第3~7号怪物受到1点伤害（加-1）
L1, R1, val1 = 3, 7, -1
diff[L1] += val1
diff[R1 + 1] -= val1

# 技能2：第5~9号怪物治疗2点（加+2）
L2, R2, val2 = 5, 9, 2
diff[L2] += val2
diff[R2 + 1] -= val2

# 前缀和还原
now = 0
for i in range(1, n + 1):
    now += diff[i]
    blood[i] = now

print("最终怪物血量变化：", blood[1:n+1])   # 输出： [0, 0, -1, -1, 1, 1, 1, 2, 2, 0]

解释：第3、4号怪物只受技能1影响，血量-1；第5~7号同时受技能1和2影响，血量=-1+2=1；第8、9号只受技能2影响，血量=2；其余0。

七、相关知识点指引

  • 前缀和：差分是前缀和的逆运算。前缀和能快速求区间和，差分能快速做区间加。两者常搭配使用。
  • 二维差分：在矩阵中处理矩形区域加减，原理类似，操作在四个角做标记。
  • 树状数组与线段树：当需要同时支持区间加和区间查询时，差分+树状数组可以做到 O(log n) 的修改和查询。
  • Differential Privacy（差分隐私）：这是一个名字相似但概念完全不同的领域，属于数据安全，注意区分。

掌握了差分，你就拥有了处理“批量区间修改”问题的利器。下次遇到类似“班主任给连续几排同学加分”“游戏里给一片区域怪物加 buff”这样的问题，记得用差分偷懒哦！

例题精讲

1单选题

对于一个长度为n的数组a，定义其差分数组d，满足d[i] = a[i] - a[i-1]（i从1开始，假设a[0]=0）。若要对区间[L, R]（1≤L≤R≤n）每个元素加上x，则差分数组应如何修改？

Ad[L] += x; d[R+1] -= x
Bd[L] -= x; d[R+1] += x
Cd[L] += x; d[R] -= x
Dd[L] -= x; d[R] += x
2单选题

使用差分数组进行多次区间修改后，最后得到原数组的复杂度是？

AO(1)
BO(n)
CO(n log n)
DO(n^2)
3判断题

对于差分数组d，其前缀和数组s（s[i]=sum_{j=1}^{i} d[j]）等于原数组a。

4填空题
给定一个长度为n的数组a（下标从1开始），现进行m次操作，每次操作将区间[L,R]每个数加上v。请补全下面的代码实现差分更新，最后输出修改后的数组。

n, m = map(int, input().split())
a = [0] + list(map(int, input().split()))
d = [0] * (n+2)
# 初始化差分数组
for i in range(1, n+1):
    d[i] = a[i] - a[i-1]
for _ in range(m):
    L, R, v = map(int, input().split())
    ___
    ___
# 还原数组
for i in range(1, n+1):
    a[i] = a[i-1] + d[i]
print(' '.join(map(str, a[1:])))
5填空题
二维差分：给定一个n行m列的矩阵a（下标从1开始），现进行q次操作，每次将子矩阵(x1,y1)到(x2,y2)每个元素加上v。请补全下面二维差分的修改代码。

d = [[0]*(m+2) for _ in range(n+2)]
# 初始化差分（略）
for _ in range(q):
    x1, y1, x2, y2, v = map(int, input().split())
    ___
    ___
    ___
    ___
# 然后求二维前缀和得到更新后的矩阵
for i in range(1, n+1):
    for j in range(1, m+1):
        d[i][j] += d[i-1][j] + d[i][j-1] - d[i-1][j-1]
    print(' '.join(map(str, d[i][1:m+1])))