差分数组是什么？为什么适合做区间批量加减？

简化版

差分数组记录相邻元素的变化量。对区间 [l, r] 加 x 时，只需要 diff[l] += x、diff[r + 1] -= x，最后对差分数组做一次前缀和就能还原结果。

详细版

差分数组适合“多次区间修改，最后统一求结果”的场景。

diff[0] = nums[0]，diff[i] = nums[i] - nums[i - 1]。
区间 [l, r] 加 x，表示从 l 开始整体抬高，r + 1 后恢复。
所以只改两个边界：diff[l] += x，如果 r + 1 < n，diff[r + 1] -= x。
所有修改完成后，对 diff 求前缀和得到最终数组。
如果需要每次修改后立刻查询，差分数组不一定够用，可能要线段树。

完整版教学

一、为什么区间修改会慢

如果要把数组 [l, r] 内每个元素都加 1，最直接做法是遍历这个区间。一次修改区间长度为 k，就是 O(k)。如果有 10 万次修改，每次覆盖 1000 个元素，就会产生 1 亿次写入。差分数组把“修改区间内每个点”的问题，变成“只标记区间起点和终点后一个位置”，从而把单次区间修改降到 O(1)。

原思路：区间里每个元素都改
差分思路：只记录从哪里开始变、从哪里恢复

记忆钩子：前缀和擅长区间查询，差分数组擅长区间修改；它们是一对反向思维。

二、差分数组到底记录什么

差分数组记录的是相邻元素的差值。diff[i] 表示 nums[i] 相比前一个元素变化了多少。如果我们知道第一个值和每一步变化量，就能一路累加还原原数组。这和爬楼梯很像：不用记录每层的绝对高度，只记录每一步上升或下降多少，也能算出每层高度。

nums: [3, 3, 5, 8]
diff: [3, 0, 2, 3]

还原：
3
3 + 0 = 3
3 + 2 = 5
5 + 3 = 8

三、为什么区间加只改两个边界

对 [l, r] 加 x，意味着从 l 位置开始，数组整体比原来高了 x；到 r + 1 位置，这个额外高度应该消失。所以在差分上只需要让 l 位置增加一个“开始抬高”的变化量，再让 r + 1 位置增加一个“恢复原状”的变化量。中间元素不需要单独改，因为前缀累加会把这个变化自动传递过去。

function add(diff, l, r, x) {
  diff[l] += x;
  if (r + 1 < diff.length) diff[r + 1] -= x;
}

四、带数字完整推演

假设初始数组全 0，长度 5，要执行两次操作：[1,3]+2，[2,4]+3。差分初始为 [0,0,0,0,0]。第一次后是 [0,2,0,0,-2]，第二次后是 [0,2,3,0,-2]，因为 r+1=5 越界，不用减。最后前缀还原得到 [0,2,5,5,3]。

步骤	diff
初始	`[0,0,0,0,0]`
`[1,3]+2`	`[0,2,0,0,-2]`
`[2,4]+3`	`[0,2,3,0,-2]`
还原	`[0,2,5,5,3]`

五、差分和前缀和的关系

差分数组对原数组做“相邻相减”，前缀和对差分数组做“连续累加”。所以它们像一组逆操作。前缀和把原数组变成适合查询的累计结构，差分把原数组变成适合修改的变化结构。掌握这层关系后，你会发现很多区间题都是在这两种视角之间切换。

nums --相邻相减--> diff
diff --前缀累加--> nums

六、什么时候差分数组不够

差分数组最适合离线场景：先收集所有区间修改，最后统一还原。如果题目要求每次修改后马上查询任意区间和，普通差分就不够，因为还原和查询可能仍然要 O(n)。这时要考虑树状数组、线段树，或者带懒标记的区间结构。面试时能说清这个边界，比只背公式更重要。

多次区间修改 + 最后输出：差分数组
多次区间修改 + 实时区间查询：线段树/树状数组变体

七、常见误区与追问

误区：差分数组直接就是最终答案。 它只是变化量，必须前缀累加还原。
误区：区间加要改区间内每个 diff。 差分只改两个边界，中间靠累加传播。
误区：r + 1 永远存在。 如果 r 已经是最后一个元素，就不能访问越界位置。
追问：差分数组能处理负数加减吗？ 能，加负数就是区间减，原理完全一样。
追问：差分和前缀和是什么关系？ 差分是相邻相减，前缀和是累加还原，两者互为逆过程。

八、加强记忆

差分数组可以记成“变化量记账”。区间加不是挨个改人，而是在起点贴一张“从这里加 x”的纸，在终点后贴一张“从这里取消 x”的纸。最后从左到右扫一遍，所有纸条效果自然叠加成最终数组。答题时讲清两个边界、一次还原和不适合实时查询这三个点，就很完整。

简化版

详细版