差分数组是个啥？能干啥？怎么用？（差分详解+例题）

差分数组很明显就是个数组呗，，，

本菜鸡学的比较浅，先说一下我自己认识的差分数组吧！

先解释一下什么是 差分：

差分其实就是数据之间的差，什么数据的差呢？就是上面所给的原始数组的相邻元素之间的差值，我们令 d[i]=a[i+1]-a[i]，一遍for循环即可将差分数组求出来。

下面给你一个栗子，给出一个差分数组先

其实差分数组是一个辅助数组，从侧面来表示给定某一数组的变化，一般用来对数组进行区间修改的操作

还是上面那个表里的栗子，我们需要进行以下操作：

1、将区间【1，4】的数值全部加上3

2、将区间【3，5】的数值全部减去5

很简单对吧，你可以进行枚举。但是如果给你的数据量是1e5，操作量1e5，限时1000ms你暴力枚举能莽的过去吗？T到你怀疑人生直接。这时我们就需要使用到差分数组了。

其实当你将原始数组中元素同时加上或者减掉某个数，那么他们的差分数组其实是不会变化的。

利用这个思想，咱们将区间缩小，缩小的例子中的区间 【1,4】吧这是你会发现只有 d[1]和d[5]发生了变化，而d[2],d[3],d[4]却保持着原样，

在进行下一个操作，

这时我们就会发现这样一个规律，当对一个区间进行增减某个值的时候，他的差分数组对应的区间左端点的值会同步变化，而他的右端点的后一个值则会相反地变化，其实这个很好理解

其实也就这么一点代码就ok了

既然我们要对区间进行修改，那么差分数组的作用一定就是求多次进行区间修改后的数组喽

注意 只能是区间元素同时增加或减少相同的数的情况才能用

因为我们的差分数组是由原始数组的相邻两项作差求出来的，即 d[i]=a[i]-a[i-1]；那么我们能不能反过来，求得一下修改过后的a[i]呢？

直接反过来即得  a[i]=a[i-1]+d[i] 

事实证明这是正确的，具体证法就不再推广，有空再补上吧；

更新数组a的方式则是下面的那一点点代码，这样我们就求出来了更新后的数组 a，是不是比线段树快多了呢？