🔥 1.什么是差分数组？
差分数组本质上和前缀和数组就是相对的。
我们直接通过两个数组来对比即可知道。
显而易见，数组b是数组a的前缀和数组。而相对而言，我们称数组a是数组b的差分数组。
🍋2.差分数组的预处理
差分数组的预处理还是非常简单的，从前缀和预处理逆过来推理即可。由我们之前学过前缀和的定义可以知道：对于任意一个数组b中的元素：
所以这个公式就是我们差分数组预处理的核心步骤，如果有原数组b[]，通过这样处理即可得到我们的差分数组a[]。
for(int i=1;i<=n;i++){ b[i]=a[i]-a[i-1]; }
🍅3.差分数组的使用
既然我们知道了如何得到差分数组，那到底差分数组有什么用呢？这个我们同样通过分析数组a和数组b之间的关系。
由于b是a的前缀和数组，所以前面我们有这样一个式子：
如果我们对某个ai加上一个常数d对b数组有什么影响？
从上面的式子可以看出来，如果ai加上了d，bi的值会加上d，那么会影响bi-1吗？肯定是没有影响的，因为bi-1的值是从a1加到ai-1。那么对bi之后的的数有影响吗？是有的，因为
bi+1是从a1加到ai+1，这其中包括了ai，所以bi+1的值也会加上d，后面的数同理。
从这样分析我们可以看出，当我们对差分数组某个数ai进行操作时，会将原数组[bi，bn]所有数都产生影响。这样可以让我们优化很多操作。
1、让原数组区间[L，R]都加上d
对于这个操作，按照朴素的做法，我们需要对原数组从L到R循环遍历过去加上d。这样的时间复杂度是O(R-L)，当区间足够长时，时间复杂度会达到O(n)，需要遍历整个数组。但如果我们原数组的差分数组进行操作时，只需要对L和R位置进行操作即可，对L位置加上d，就会使得原数组从L开始全部数加上d，对R+1位置减去d，就会使得原数组从R+1开始所有的数减去d，综合起来就能让原数组[L，R]区间都加上d。这样无论L到R的范围有多大，我们只需要对两个位置进行操作，时间复杂度稳定到O(1)。
核心操作：
public static void insert(int l,int r,int c,int[] b){ b[l]+=c; b[r+1]-=c; }
🌸4.模板题解析
由于对原数组操作复杂度过高，我们先得到差分数组，然后对差分数组进行操作，最后操作完毕后再对原数组进行复原即可，复原的操作就是获得前缀和数组。
代码转换：
import java.util.Scanner; import java.io.*; class Main{ static BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out)); public static void main(String[] args)throws Exception{ Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int m=sc.nextInt(); //原数组 int[] a=new int[n+1]; //差分数组,开n+2的长度，防止在insert中b[r+1]时数组越界 int[] b=new int[n+2]; for(int i=1;i<n+1;++i){ a[i]=sc.nextInt(); } //获取差分数组 for(int i=1;i<n+1;i++){ b[i]=a[i]-a[i-1]; } while(m-->0){ int l=sc.nextInt(); int r=sc.nextInt(); int c=sc.nextInt(); insert(l,r,c,b); } //读回原数组a for(int i=1;i<n+1;i++){ a[i]=a[i-1]+b[i]; log.write(a[i]+" "); log.flush(); } } //核心操作 public static void insert(int l,int r,int c,int[] b){ b[l]+=c; b[r+1]-=c; } }
