前缀和负责"快速查询区间的和"，差分负责反过来——"快速修改一整段区间"。
上一节前缀和解决的是"原数组不变，反复查询某一段的和"——但如果反过来，题目要反复对数组做"给第 L 到第 R 个数都加上 v"这种操作呢？直接写循环，把区间里每个数都加一遍，单次操作要花 O(区间长度) 的时间——如果区间很长、操作次数又很多，照样会很慢。
差分就是用来解决这个问题的：它能把"给一整段区间加 v"这件事，变成只需要修改两个位置，时间复杂度直接降到 O(1)。
差分数组 diff 记录的是相邻两个数之间的差距：diff[i] = arr[i] - arr[i-1]（约定 arr[0] = 0）。可以把原数组想象成一排台阶，每一级台阶相对上一级"升高了多少"或"降低了多少"，正是 diff 数组存的内容。
0）；从第 2 级到第 3 级，突然升高了 3（5-2=3）；第 3、4 级之间没有变化；第 5 级到第 6 级，又降低了 2（3-5=-2）。diff 数组只关心"每一步升降了多少"，不关心台阶的绝对高度——这正是它能高效处理"区间统一升降"的关键。diff 数组；反过来对 diff 数组求前缀和，正好能还原出原数组——diff[1]+diff[2]+...+diff[i] 算出来就是 arr[i]。这一点很重要：差分数组本身不是用来"看"的，它是一个中间工具，最终都要通过前缀和还原成真正的数组。现在看核心操作：给原数组第 L 到第 R 个数都加上 v，在差分数组上只需要两步：diff[L] += v，diff[R+1] -= v。
用"台阶"来理解：从第 L 级开始，往后每一级都要比原来高 v——这件事只需要在第 L 级"垫高" v（diff[L] += v），后面的台阶因为是"接着上一级往上叠"的，会自动跟着一起抬高，不需要逐个去改；而第 R 级之后不应该再继续抬高了，所以要在第 R+1 级"退回去" v（diff[R+1] -= v），把多出来的高度抵消掉，让 R 之后的台阶恢复到原来的相对高度。
| 1 | void RangeAdd(int diff[], int l, int r, int v) |
| 2 | { |
| 3 | diff[l] += v; // 从第l个数开始，整体抬高v |
| 4 | diff[r + 1] -= v; // 第r+1个数开始，把多出来的v退回去 |
| 5 | } |
用一个长度 8、初始全是 0 的数组演示，依次做 3 次区间加法：
+v，粉色是 -v），不管区间多长，代价都一样。3 次操作做完之后，对 diff 数组求一次前缀和，就能直接还原出最终的数组 {-1,2,2,5,5,2,2,0}——和真的去逐个执行 3 次区间加法、暴力模拟出来的结果完全一致。| 1 | int result[n + 1] = {0}; |
| 2 | for (int i = 1; i <= n; i++) |
| 3 | { |
| 4 | result[i] = result[i - 1] + diff[i]; // 和5.1节求前缀和的写法完全一样 |
| 5 | } |
假设数组长度 n=1000，一共要做 1000 次区间加法操作（每次区间长度平均按 500 估算）：
1000 次操作、每次平均改 500 个数，总共约 50万 次；差分每次操作只改 2 个位置（1000×2=2000 次），最后再花一次 O(n) 还原出最终数组（1000 次），总共约 3000 次——快了 160 倍以上。| 做法 | 单次区间加法 | q 次操作总复杂度 |
|---|---|---|
| 直接修改区间 | O(区间长度) | O(n × q)（最坏情况） |
| 差分 | O(1) | O(n + q) |