入门 · 算法 · 约 18 分钟
差分数组 在左边开始，在右边停止
一次区间加法，只记两个边界；最后累加，还原每一项。 跳到探测器进阶实验 ↓
D[1] += 3；D[4] −= 3 extra[i] = Σ D[0..i]
1/8 · 先圈出 [1,4)，每项都加 3。
方向键 / Home / End 调整滑块。改变输入会回到第一步；两段重叠的增量相加。D 是“额外增量”的差分，初始全 0；原数组 A 单独保存。
同一组输入，完整代码与结果
const a = [2, -1, 3, 0, 2, -2];
const d = Array(a.length + 1).fill(0);
d[1] += 3; d[4] -= 3; // [1,4)
let extra = 0;
const b = a.map((value, i) => {
extra += d[i];
return value + extra;
});
// d = [0, 3, 0, 0, -3, 0, 0]
// b = [2, 2, 6, 3, 2, -2]右端 r=n 时，取消标记写入 D[n]；还原只扫描 i=0 到 n−1，不输出哨兵。完整代码展示最终结果，上方逐步观察它怎样得到。
看完图，带走这些结论
对零基左闭右开区间 [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]仅用于取消到数组末尾的影响。
逐步例子
- 原数组 A=[2,−1,3,0,2,−2]。给 [1,4) 每项加3，目标仅是下标1、2、3，最终应得到 [2,2,6,3,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]。
- 逐格累加 D：extra=[0,3,3,3,0,0]。每次先执行 extra+=D[i]，再算 B[i]=A[i]+extra；不能先写结果再更新 extra。
- 为什么成立？一个更新在位置i的贡献是 v·1(i≥l)−v·1(i≥r)。i<l 时两项都为0；l≤i<r 时只有第一项；i≥r 时两项抵消。多次更新按加法叠加，因此次序不影响最终结果。
- 再给 [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。
- 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)时间和空间，不能套用普通标量差分的复杂度。
参考资料
进阶实验：覆盖数量相同，能认出位置吗？
每条横带是一台独立探测器。它只报告“在范围内 / 不在范围内”。先沿竖线扫描，再比较：把所有报告加成一个数量，会丢掉什么？这里使用一基闭区间 [l,r]，停止事件放在 r+1，等价于半开区间 [l,r+1)。
位置 1：覆盖数 0 + 边界净变化 1 = 1；报告 100
第 1/6 个位置：先停止 无，再启动 探测器1；现在有效：探测器1。
实心成员圆表示有效，空心表示无效；报告从左到右按探测器编号排列，不是二进制整数。虚线延伸到 r+1 仅表示停止事件，不表示继续覆盖。方向键 / Home / End 调整滑块，修改后回到位置1。最后的 n+1 是哨兵，不是待区分位置。
// 对每台探测器 j 的闭区间 [l,r]
start[l].push(j); stop[r + 1].push(j);
// 当前 x = 1，事件先于报告
for (j of stop[x]) active.delete(j); // 无
for (j of start[x]) active.add(j); // 探测器1
report = detectors.map(j => active.has(j) ? 1 : 0);
count = active.size; // 1，report = 100当前全部位置的报告互不相同，可以区分每个位置。只报告数量则还可能合并原本不同的报告。时间 O(n(k+1)+k)，空间 O(n(k+1)+k)，这里展示完整 n×k 报告表，不冒称普通标量差分的 O(n+k)。
不操作也能读懂：为何“都是 2”还不够？
默认三段 [1,3]、[2,4]、[3,5] 在六个位置给出 100、110、111、011、001、000。位置2与4覆盖数都是2，但前者属于第1、2台，后者属于第2、3台。标量差分能正确还原总数，却不能从总数逆推出探测器身份。这是信息被求和丢失，不是差分算错。
每台分别记开始与停止、维护有效编号集合，就能得到完整报告。即使某处一台停止、另一台开始，净变化为0，也必须处理两条身份事件。重复区间得到相同的成员变化；空集合在 n=1 时足够区分唯一位置，在 n>1 时则不够。
练习背景：Codeforces 2261 D1 官方题解。这里只解释确定性的区间身份与边界事件，不使用随机哈希，也不展开 D2。这个拓展不改变上方批量区间加法的用法。