差分算法（java）

一、差分的核心：记录「变化量」而非「具体值」

先举个生活例子，你就懂了：假设你有一本记账本，记录每天的零花钱：

• 第 1 天：5 元
• 第 2 天：7 元
• 第 3 天：7 元
• 第 4 天：10 元

如果用「普通记录法」（对应原数组），就是记[5,7,7,10]；如果用「差分记录法」，只记当天比前一天多了多少（前一天默认 0）：

• 第 1 天：5 - 0 = 5 元（比第 0 天多 5）
• 第 2 天：7 - 5 = 2 元（比第 1 天多 2）
• 第 3 天：7 - 7 = 0 元（比第 2 天没多）
• 第 4 天：10 - 7 = 3 元（比第 3 天多 3）

最终差分记录的数组（差分数组）就是[5,2,0,3]。

一句话总结差分：差分数组d是原数组a的「相邻变化量数组」，核心公式（下标从 1 开始）：d[i] = a[i] - a[i-1]（a[0]默认为 0）。

反过来，知道差分数组也能还原原数组：把差分数组从头累加（算前缀和）就行。比如上面的差分数组[5,2,0,3]：

• 第 1 天：5（累加第 1 个）
• 第 2 天：5+2=7（累加前 2 个）
• 第 3 天：5+2+0=7（累加前 3 个）
• 第 4 天：5+2+0+3=10（累加前 4 个）刚好还原出原数组，这就是差分的「可逆性」。

二、差分的真正价值：快速改区间

差分不是为了记录数据，而是为了高效修改区间值—— 这也是竞赛里用它的核心原因。

还是用零花钱举例：如果想给「第 2 天到第 4 天」每天的零花钱都加 3 元，两种做法对比：

1. 普通做法：直接改原数组，需要改 3 个位置：第 2 天：7+3=10，第 3 天：7+3=10，第 4 天：10+3=13 → 改 3 次。
2. 差分做法：只改差分数组的 2 个位置，最后还原就行：
   • 想让「第 2 天开始」都加 3 → 差分数组第 2 位 +3（d[2] = 2+3=5）；
   • 想让「第 5 天（4+1）停止」加 3 → 差分数组第 5 位 -3（但这里只有 4 天，不用管）；改完差分数组是[5,5,0,3]，还原后：第 1 天：5，第 2 天：5+5=10，第 3 天：10+0=10，第 4 天：10+3=13 → 结果一样，但只改了 2 次！

如果区间是「第 2 天到第 10000 天」，普通做法要改 9999 次，差分还是只改 2 次 —— 这就是效率的天壤之别！

三、差分改区间的通用规则（必记）

对原数组的区间[l, r]所有数加val，只需对差分数组做：

1. d[l] += val（从 l 开始，后面都加 val）；
2. d[r+1] -= val（到 r 结束，r+1 开始取消加 val）。

（如果 r 是数组最后一位，d[r+1]可以不管，因为超出数组范围了，不影响还原）

总结

1. 差分本质是记录「原数组相邻元素的变化量」，而非具体值；
2. 差分的核心优势是：修改区间值只需操作 2 个位置，时间复杂度从 O (n) 降到 O (1)；
3. 差分数组能通过「前缀和」还原出原数组，是可逆的。

简单说，差分就是为了「批量改区间」而生的工具，竞赛里遇到「给某个区间所有数加 / 减一个值」的题，优先想差分准没错！