一维差分算法篇：高效处置惩罚区间加减

那么在正式先容我们的一维差分的原理前，我们先来看一下一维差分所应用的一个场景，那么假设我们现在有一个区间为[L,R]的一个数组，那么我要在这个数组中的某个子区间好比[i,m] (L<=i<=m<=R)举行一个加k值大概减去k值的一个利用，那么我们通例的暴力方法就是我们直接遍历一遍该数组的子区间每个位置加k大概每个位置减k，那么一旦该利用多了，那么对数组的遍历就过于频仍，那么我们能不能用一个较小的代价来完成这每个区间的加k值大概减k值的全部利用而不是每次都去遍历一遍数组呢，那么我们的一维差分就能做到这一点。
1.一维差分原理

那么我们现在有一个区间为[L,R]的一个数组，那么我们要在此中的恣意的子区间加k大概减k，那么这里我们目的是想得到我们这个数组从原始状态颠末该利用后也就是在恣意子区间加减k值后的一个终极状态，那么我们对这个数组的恣意子区间的加减利用我们可以明白为我们要在数组原状态下所叠加的状态，那么假如我们可以大概知道我们数组各种叠加状态后的综合得到的一个终极的叠加状态，那么我们数组在此根本上只须要叠加一个综合的叠加状态那么就可以得到终极状态了。
这里我们照旧举一个例子来表明一下我刚才的一个观点，那么假设我们有长度为10的一个原数组[1,2,3,4,5,6,7,8,9,10],那么这里假设我们对这个[0,9]区间的数组中的[0,4]地区处团体减去3，在[0,2]地区处团体加2，末了在[3,5]地区处团体加1，那么我们要知道在这三个利用下我们数组终极的状态的各个位置的值是怎样的
那么我们这里可以把我们数组最开始的形态：[1,2,3,4,5,6,7,8,9]视作初始状态，而我们这三次利用好比在[0,4]地区处团体减去3，视作我们要叠加的状态，那么这里我们假如要得到我们的目的数组，我们肯定是分别叠加三次要叠加的状态，好比在[0,4]减3，然后再[0,2]地区加二，末了在[3,5]地区加1，终极得到我们数组的终极状态也就是[0,1,2,2,3,5,6,7,8,9],那么现在我们盼望就是只用叠加一次状态就得到我们的终极状态，那么这里我们只用叠加一次，那么也就意味着我们要知道这三次叠加状态的一个综合效果。
那么这里得到这里所谓的综合得到的叠加状态，就是通过创建一个差分数组diff，该数组的下标就对应我们原始数组的相应位置，那么此中的每个位置的值则体现我们原始数组中对应位置终极该叠加的一个状态也就是[-1,-1,-1,-2,-2,0,0,0,0,0]，那么我们原始数组每个位置加上对应的值就可以大概得到我们终极状态也就是[0,1,2,2,3,5,6,7,8,9]，也就只须要遍历一遍数组即可。
以是现在的疑问就变化为了怎样加载这个差分数组diff，那么这里我们假设我们要在区间[L,R]中的子区间[i,m]处加v，那么这里我们须要一个与我们原始数组长度对应的一个差分数组，然后将其初始化每个位置的巨细都为0，然后我们这里只须要在下标为i位置处加v，然后再m+1处加-v，然后对该差分数组加载对应的一份前缀和数组，那么我们就可以把前缀和数组中区间[i,m]的团体的值给全部刷成v，那么我们对于区间[i,m]的每个位置上的数要叠加的状态就是该区间的每个数加v，那么我们通过这两步就能得到区间[i,m]的叠加状态。
看到这里你想必肯定有两个疑问，第一问是想问我为什么要在i位置处加v，在m+1位置处要减去v？第二问则是为什么加工一遍前缀和就可以大概得到该利用下的叠加状态？
这里我们知道我们的叠加状态就是对整个区间同一举行加大概减去定值k，那么这里我们要得到该状态所对应的差分数组的话，那么差分数组中对应[i,m]的值肯定全部是k大概-k，那么这里我们怎样将差分数组中的[i,m]全部设置为k大概-k呢，固然肯定不是通过遍历，而这时间前缀和派上用场了，由于我们前缀和的盘算公式是sum=sum[i-1]+arr，那么我们发现假如我们在i位置处加一个v，那么根据前缀和的公式：sum+v=sum[i-1]+(arr+v),那么此时i位置加v之前对于第i+1位置的前缀和是：sum[i+1]=sum+arr[i+1],但是我们由于i位置加了一个v，那么sum此时的值是sum+v,那么对于sum[i+1]来说，由于sum[i+1]=sum+arr[i+1],而现在sum的值酿成了sum+v，以是sum[i+1]的值就酿成了sum[i+1]+v,那么我们可以依次类推：

那么这里我着实就可以观察到我们在i位置处加v，然后加工一遍前缀和，我们包罗i位置在内以及之后的每一个前缀和都会加v，那么这个加v的效果会连续到包罗i位置在内的右侧的全部区间，那么根据我们上面的式子，由于我们差分数组的每个数初始化为0，那么也就意味着我们在sum的前缀和是0，那么我们假如不加v的话，那么我们这个差分数组加工得到的前缀和数组的每个位置都是0,但是由于我们这里在i位置加了v，那么我们知道我们在包罗i位置之后的右侧区间全部会刷成v，但是我们只要[i,m]处刷成v，那么我们得到m位置之后抵消这个加v的效果，那么我们就在m+1位置从设置-v，那么我们m+1以及右侧的位置都会有一个加-v的效果，那么与前面的抵消了，以是这就是为什么我们在i位置处设置v,m+1位置处设置-v，然后加工一遍前缀和的缘故因由。

那么我们假如在[i,m]区间处减去v的话，只要你看懂我们上面的原理，那么就不消我再去解说赘述了，以是我们对于多次如许的利用，好比在某个区间[i,m]加v大概减去v，那么我们就根据上文讲的原理，在对应位置处i位置加大概减去v，然后再相应的m+1位置处减大概加v，然后加工一遍前缀和，就能得到这全部利用综合的叠加状态了

---

那么这里着实代码模版就很简单，就是一个差分数组和对应加工的前缀和数组，只不外这里在实现的时间留意边界题目，由于我们假如在好比[i,R]区间上加v大概减v，R是我们这个数组的右边界，那么我们的差分数组假如跟原数组长度一样的话，那么根据刚才的原理，我们会在R+1位置处减v大概加v，那么为了不越界的话，我们会加上一些条件判定，但是假如你不想讨论边界的话，你的差分数组的长度就可以比原数组大一个单位，也就是原数组的长度是n，那么你的差分数组1长度就是n+1，然后按照刚才的思绪去在相应的位置设置值，末了只须要加工一遍前缀和即可。
公式：
在[i,m]同一加v：diff+v  diff[m+1]-v
在[i.m]同一减v：diff-v    diff[m+1]+v
代码实现：

1. #include <iostream>
2. #include <vector>
3. using namespace std;
5. int main() {
6.     vector<int> arr(10) = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
7.     vector<int> diff(arr.size() + 1, 0); // 差分数组长度应为原数组长度+1
9.     // 假设要在[0,3]区间加3，在[2,4]区间减2
10.     diff[0] += 3;
11.     diff[4] -= 3; // 注意这里是4，因为区间是[0,3]，所以结束位置+1
12.     diff[2] -= 2;
13.     diff[5] += 2; // 同样，区间是[2,4]，所以结束位置+1
15.     vector<int> diffsum(arr.size()+1, 0);
17.     for (int i = 1; i < arr.size(); i++) {
18.         diffsum[i] = diffsum[i - 1] + diff[i-1];
19.     }
20.     return 0；
21. }

复制代码

那么很多人看完这个一维差分，感觉差分不是很高效，我们加载一遍前缀和意味着要遍历一遍数组，那么复杂度是o(N),那么假如说我们只是对区间[L,R]的数组中某个子区间同一的加或减去v，那么根绝还不如我直接遍历这个子区间高效，但是我们差分数组在面临如许的场景，好比你这里要对数组的子区间举行100次以致1000多次的加v大概减v利用，假如这个数组还特别长的话，那么此时长分就只须要遍历一遍数组即可，以是此时差分的良好就体现出了
2.等差数列差分

那么我们这里有一个特别的差分也就是等差数列差分，那么我们这里假设要在区间[i,m]中叠加的状态是一个等差数列，那么该等差数列首项是s，公差是d，那么i位置是s，以后依次是s+d，s+2d，以是终极的叠加状态：
[s,s+d,s+2d,s+3d,…,s+(i-m)*d]
那么这里我们要得到该叠加状态着实我们加载一遍前缀和是不敷的，由于一边前缀和只能将区间刷成一个同一的值好比s好比d，那么这里一遍不敷，那么也就意味着我们要加载双方前缀和，那么这里我们要得到我们加载双方前缀和数组的初始差分数组的形态，那么我们就采取逆推
我们这里先推终极叠加状态的上一级状态也就是中心状态，那么我们这里[i.m]每个位置都有首项s，那么这里我们的i位置就得加上s，然后m+1位置处减去s,那么这里由于我们这里i+1到n处的d是依次递增的，那么我们这里i+1到m处肯定都有一个d值，如许加载前缀和，前面的加d的效果到背面一个位置，那么在加上背面本身有一个d，那么该位置就得到2d，那么在以后转达，就能做到递增，但是要在m之后的区间抵消，那么我们就得在m+1位置处减去(i-m)*d
那么我们要得到中心状态，也就是[s,d,d,d,d,d,d,…，-（s+(i-m)*d）]那么我们则须要在l位置设置为s，l+1位置处设置为d-s，然后m+1位置处设置为-(s+(i-m))*d),然后我们加工两遍前缀和数组即可
代码实现：

1. #include <iostream>
2. #include <vector>
3. using namespace std;
5. int main() {
6.     int n = 10; // 数组长度
7.     int i = 2;  // 区间起始位置
8.     int m = 5;  // 区间结束位置
9.     int s = 3;  // 等差数列首项
10.     int d = 2;  // 等差数列公差
12.     vector<int> arr(n, 0); // 原始数组
13.     vector<int> diff(n + 1, 0); // 差分数组
15.     // 初始化差分数组
16.     diff[i] += s;
17.     if (i + 1 <= m) {
18.         diff[i + 1] += -s + d;
19.     }
20.     if (m + 1 < n) {
21.         diff[m + 1] -= s + (m - i) * d;
22.     }
24.     // 第一次前缀和，得到中间状态
25.     vector<int> mid(n, 0);
26.     diff[0]=0
27.     for (int j = 0; j < n; j++) {
28.         mid[j] = mid[j] + diff[j];
29.     }
31.     // 第二次前缀和，得到最终状态
32.     vector<int> result(n, 0);
33.     result[0] = mid[0];
34.     for (int j = 1; j < n; j++) {
35.         result[j] = result[j - 1] + mid[j];
36.     }
37.     return 0;
38. }

复制代码

3.结语

那么我们差分是我们处置惩罚区间加减利用的一个非经常用高效的一个算法，那么这里的差分我们是一维差分，那么既然都说了是一维差分，那么肯定就有二维差分，那么我们相识了一维差分的原理之后，那么着实二维差分我们也大概知道它的用途，那么就是针对于二维数组某个地区的同一的加减题目，那么我会在之后的文章中会解说我们的二维差分以及二维差分须要用到的二维前缀和，那么盼望本文可以大概让你有所劳绩，我会连续更新，也盼望你多多关注与支持，你的支持就是我最大的动力！

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。