# 差分数组图解：区间加法，只记开始与结束

把整段加法变成两个边界事件，逐格累加还原增量；看懂右端哨兵、重叠更新、负增量与空区间，再用探测器泳道理解覆盖数量为何丢失成员身份。

原文 / Canonical: https://crazycloud.cc/learn/difference-array
作者: crazycloudcc
首次发布: 2026-10-17
更新: 2026-10-21

本阅读版与网页共用课程数据；互动请访问原文。

## 一句话答案

对零基左闭右开区间 [l,r) 的每项加 v，可在全零增量差分 D 上做 D[l]+=v、D[r]−=v。最后从左到右累加 D，得到每项的额外增量，再加回原数组 A。左端开始生效，右端取消，所以 r 不包含在修改范围内。

## 适用条件与边界

先收集全部区间加法，再一次还原最终数组；n≥1，0≤l≤r≤n，边界为整数。D 长度为 n+1，初始全零，只记录额外增量；它不是原数组 A 的差分。实验固定六项小整数，最多叠加两次，计算精确。数学上允许负增量与空区间，不要求原数组有序。

## 不变量

扫描完 D[i] 后，extra 等于所有满足 l≤i<r 的更新增量之和；B[i]=A[i]+extra。D[n]仅用于取消到数组末尾的影响。

## 逐步例子

1. 原数组 A=[2,−1,3,0,2,−2]。给 [1,4) 每项加3，目标仅是下标1、2、3，最终应得到 [2,2,6,3,2,−2]。
2. 先令 D=[0,0,0,0,0,0,0]。D[1]+=3 表示从边界1开始多加3；D[4]−=3 表示到边界4停止。得到 D=[0,3,0,0,−3,0,0]。
3. 逐格累加 D：extra=[0,3,3,3,0,0]。每次先执行 extra+=D[i]，再算 B[i]=A[i]+extra；不能先写结果再更新 extra。
4. 为什么成立？一个更新在位置i的贡献是 v·1(i≥l)−v·1(i≥r)。i<l 时两项都为0；l≤i<r 时只有第一项；i≥r 时两项抵消。多次更新按加法叠加，因此次序不影响最终结果。
5. 再给 [3,6) 加−2：D=[0,3,0,−2,−3,0,2]，extra=[0,3,3,1,−2,−2]，结果 [2,2,6,1,0,−4]。重叠位置3得到3+(−2)=1，而不是覆盖为−2。
6. r=n 时把取消事件写入 D[n]，但只还原 n 个元素。l=r 时两次修改落在同一位置并相互抵消；v=0 同样不改变任何值。

## 批量更新、还原与数值范围

初始化 D 为 O(n)，每次区间加法记录两个边界为 O(1)，q 次记录后统一还原 O(n)，总时间 O(n+q)，额外空间 O(n)，按单位成本整数算术计算。单次记录快，不等于每次更新后都能立即 O(1) 得到任意最终值；交错查询通常需要树状数组或线段树等结构。AtCoder AWC0173 D 最多10⁵次、每次伤害10⁹，单点累计可达10¹⁴，超过32位有符号整数；C++应使用long long。JavaScript对该上界整数仍精确，但不能推广到任意大数。

## 常见误区

- 本课用[l,r)，所以在r处减v；零基闭区间[l,r]才在r+1处减v。题目一基闭区间[L,R]应转成本课[L−1,R)。
- 只分配n项却写D[n]：右端哨兵需要n+1项；哨兵不是额外的原数组元素。
- 把D当结果：D是增量变化事件，要做前缀累加，再加原值A[i]。
- 混用两种构造：若D已经是原数组的差分，前缀还原就得到原值，不应再次加A。本课始终把原值与增量分开。
- 用赋值替代+=或−=：多次更新共用边界时必须累加，重叠段也会叠加。
- 把批量最终求值当在线查询：每次都重扫n项会变成O(nq)，不能仍声称总计O(n+q)。

## 自测

六项数组只把最后一项减2，两个事件放哪里？[3,3)加5会怎样？有两次同为[1,4)加3，能用赋值覆盖D吗？

最后一项是[5,6)，记录D[5]−=2、D[6]+=2，哨兵不输出。[3,3)的加5与减5在同一位置抵消。两次相同更新应叠加成每项加6，不能用赋值覆盖。

## 可选进阶：方案验算与探测器身份

差分能快速验算一组区间操作，却不会替你选出最便宜的一组。2026-10-20 已结束的 AtCoder AWC0182 D 给出至多15张卷轴：每张只能使用一次，花费W，对一基闭区间[L,R]造成C点伤害。要求全部怪物受到的总伤害不少于生命值，并使花费最小。小的是卷轴数M，不是生命值；可以枚举2ᴹ个子集，再用差分检查每个候选。本段是静态进阶应用，上方图形和同步代码仍演示批量区间加法。

对每个候选，从全零、长度N+1的D重新开始。选中一张卷轴便记录D[L−1]+=C、D[R]−=C，并累加W；随后从i=0到N−1累加damage+=D[i]。只有每个位置都满足damage≥A[i]，这个候选才可行，才能更新最小花费。这里D还原的是伤害，不是剩余生命；不要再加A，也不要把上一个候选的D沿用下来。所有子集都不可行时返回−1。原题生命值为正，空子集虽须纳入枚举，但一定不能击败全部怪物。

例如生命值[3,4,2]，三张卷轴分别是([1,2],伤害3,花费4)、([2,3],伤害2,花费3)、([1,3],伤害4,花费8)。选前两张的零基事件为D=[3,2,−3,−2]，累加伤害[3,5,2]，花费7，全部达标。第三张单独也可行但花费8；前两张单独都漏掉一个端点，因此最优是7。范围相交时伤害相加，不是取最大；恰好等于生命值也算击败。右端R=N的取消事件仍写D[N]，但不把哨兵当怪物检查。

每个子集清零和还原需O(N)，检查M张卷轴并记录边界需O(M)，总时间O(2ᴹ(N+M))、额外空间O(N+M)，不保证任意大的M也可用。题目N≤200、M≤15，所以最多32768个子集；这不是在线区间查询，也不需要为每个子集建一棵树。伤害与花费的总量各至多15×10⁹，超过32位有符号整数，C++应使用long long；这些边界内JavaScript Number整数精确，但不要用位运算累加伤害或花费。事件符号可为负，不等于卷轴造成负伤害。赛事日期说明来源的新近性，不代表已核实搜索热度或流量增长。

另一个图形实验保留探测器身份：一基闭区间[1,3]、[2,4]、[3,5]给六个位置的报告依次为100、110、111、011、001、000，位顺序按探测器1、2、3。位置2与4的覆盖数均为2，但成员不同；标量差分还原的是总数，不能从总数反推身份。为每台在l启动、r+1停止并维护有效编号集合，才可还原完整报告。同处停止一台并启动另一台时净变化为0，身份仍改变。网页下方泳道可逐步观察；没有探测器时n=1的空报告足够，n>1则无法区分。完整报告表实现需O(n(k+1)+k)时间和空间，不能套用普通标量差分的复杂度。

## 延伸学习

前缀和把局部数值累加为整体；差分记录变化发生的位置，再用前缀累加还原每项增量。本课的D只记录额外增量，原数组另行相加。

[前置：前缀和如何累加](https://crazycloud.cc/learn/prefix-sum)

## 参考资料

- [Codeforces 2261 D1：区间探测器官方题解](https://codeforces.com/blog/entry/157917)
- [AtCoder AWC0182 D：Sweeping Out Monsters（2026-10-20赛后应用）](https://atcoder.jp/contests/awc0182/tasks/awc0182_d)
- [官方题解：子集枚举与Imos差分](https://atcoder.jp/contests/awc0182/editorial/26661)
- [AtCoder AWC0173 D：Monster Subjugation（批量范围攻击，2026-10-07）](https://atcoder.jp/contests/awc0173/tasks/awc0173_d)

[返回图解实验室](https://crazycloud.cc/learn)