插旗子法

一、 痛点：被“区间修改”支配的恐惧

在刷算法题时，我们经常会遇到这样一种场景：

给你一个长度为N NN的数组（初始全为 0），接着有Q QQ次操作，每次操作要求你把区间[L, R]内的所有元素都加上一个数C CC。最后问你数组里的每个元素变成了多少？

小白的直觉做法（暴力循环）：

// q 次操作for(inti=0;i<q;i++){// 每次把区间 [L, R] 里的数都 +1for(intj=L;j<=R;j++){arr[j]++;}}

后果是什么？
如果N = 200 , 000 N = 200,000N=200,000且Q = 200 , 000 Q = 200,000Q=200,000。最坏情况下，你的程序要跑20 万 × 20 万 = 400 亿 20万 \times 20万 = 400亿20万×20万=400亿次循环！提交上去绝对是红色的Time Limit Exceeded (TLE)。

那么，有没有什么办法，能让我们不用一遍遍地去循环修改中间的数字呢？
这就是差分数组大显身手的时候了！

二、 核心思想：“插旗子”法

理解差分数组，我们先抛开枯燥的数学公式，想象一个**“刷墙”**的场景：

假设有一面 10 米长的墙，老板让你把第 3 米到第 7 米刷成红色（也就是区间[3, 7]加上 1）。

• 普通人的做法：拿着刷子走到第 3 米，刷一米，走到第 4 米，刷一米…一直刷到第 7 米。（耗时耗力）
• 聪明人的做法（差分）：在第 3 米处插一个小旗子写着“从这里开始刷 (+1)”，在第 8 米处（7的下一米）插一个小旗子写着“到这里停止刷 (-1)”。

当你把所有刷墙任务的“旗子”都插好后，最后雇一个人从第 1 米走到最后，手里拿着计算器，看到+1就加上，看到-1就减去，他手里计算器的数字，就是这一段墙应该被刷的次数！

三、 图解差分数组

我们把刚刚的“插旗子”翻译成数组操作：

我们要对区间[3, 7]进行+1操作。
我们不去循环，只做两件事：

1. diff[3] += 1（开头 +1）
2. diff[8] -= 1（结尾的下一位 -1，因为区间在 7 就结束了）

操作完后，我们的diff差分数组变成了这样：

见证奇迹的时刻：如何还原成真实的数组？
我们只需要从左到右扫一遍，做一个累加（求前缀和）：

• 位置 1：0
• 位置 2：0 + 0 = 0
• 位置 3：0+ 1= 1(受到开头旗子的影响，变成 1 啦！)
• 位置 4：1 + 0 = 1
• 位置 5：1 + 0 = 1
• 位置 6：1 + 0 = 1
• 位置 7：1 + 0 = 1
• 位置 8：1- 1= 0(受到结束旗子的影响，变回 0 啦！)
• 位置 9：0 + 0 = 0

你看！通过只修改两个端点，加上最后的一次累加，我们完美实现了区间[3, 7]全部+1的效果！

四、 代码模板

这里提供一个标准 Java 模板。时间复杂度直接从O ( N × Q ) O(N \times Q)O(N×Q)降维打击到了O ( N + Q ) O(N + Q)O(N+Q)！

publicclassDifferenceArrayDemo{publicstaticvoidmain(String[]args){intlength=10;// 数组长度// 差分数组的长度最好开大一点，防止 R+1 导致数组越界int[]diff=newint[length+2];// 模拟 3 次区间操作// 操作1：区间 [2, 5] 加上 1add(diff,2,5,1);// 操作2：区间 [4, 7] 加上 2add(diff,4,7,2);// 操作3：区间 [1, 3] 减去 1add(diff,1,3,-1);// 最后：通过前缀和还原真实数组int[]result=newint[length+1];intcurrent=0;for(inti=1;i<=length;i++){current+=diff[i];// 累加当前的标记result[i]=current;// 这就是位置 i 经过所有操作后的真实值System.out.print(result[i]+" ");}}/** * 差分数组核心方法：区间修改 * 在 [L, R] 范围内加上 val */publicstaticvoidadd(int[]diff,intL,intR,intval){diff[L]+=val;// 起点加上 valdiff[R+1]-=val;// 终点的后一位减去 val}}

五、 总结与避坑指南

1. 什么时候用差分数组？
   • 只要题目出现**“频繁对一个区间进行加减操作”，且“最后才询问数组的最终状态”**，无脑用差分数组！
2. 差分和前缀和是好兄弟：
   • 差分是前缀和的逆运算。
   • 差分负责把O ( N ) O(N)O(N)的区间修改变成O ( 1 ) O(1)O(1)。
   • 前缀和负责最后扫尾，把差分数组还原成真实数据。
3. 注意数组越界：
   • 因为我们要操作diff[R + 1]，所以初始化差分数组时，大小一定要比题目给定的最大范围多加 2，避免ArrayIndexOutOfBoundsException。
4. 局限性：
   • 差分数组属于离线算法。也就是说，你必须把所有的“修改操作”都搞完，最后才能统一看结果。如果你在操作的中间就想问“某个数字现在是多少”，差分数组就不太行了（这种场景需要用到高级数据结构：线段树或树状数组）。

作者的话：
以前遇到计数或区间修改问题，我总想着使用 HashMap 或者直接 for 循环遍历计数，结果总是被大数据量教做人（TLE 或 MLE）。直到学会了差分数组，才感叹算法设计的巧妙！把对一条线的修改，转化为对两个点的标记，这不纯纯编程里的“降维打击”吗！

以前遇到计数或区间修改问题，我总想着使用 HashMap 或者直接 for 循环遍历计数，结果总是被大数据量教做人（TLE 或 MLE）。直到学会了差分数组，才感叹算法设计的巧妙！把对一条线的修改，转化为对两个点的标记，这不纯纯编程里的“降维打击”吗！