题目链接： 【模板】差分

2.利用差分数组解决 m 次修改操作

让我们来推导一下这个性质，上图a代表原始数组，f 代表差分数组，a数组里面L到R区域里的所有元素已经加上了一个k，三角形的值是不变的，因为在给a数组L到R区域里面更改数据的时候，它们是不受影响的；

现在来看看 f 差分数组里面是怎么把这个值给更改的，f 数组里L指向的位置存放的值应该等于a数组里L指向的位置里的值减去前面的一个格子，a数组里面既然增加一个k，所以当前格子减完前面一个格子之后，它的差也是增加 k 的，所以 f 数组L位置存放的值就是k，比如之前是a3-a2，当前a3的值加上了一个k，那么再减去a2之后就比之前的差值多了k；后面的格子是a数组L+1位置减去L位置，代入数字原本是3-1，现在各自都加了1变成4-2，3-1=4-2=2，他们的差值是不变的，所以 f 组里L +1的位置修改值是0，之前的值是多少现在就是多少；同理后面也是不变的，i 和 i - 1的位置，因为它们双方都加了一个k，所以它们两个值做差依旧是不变的，但是R+1的格子需要修改，它是在a数组里面R+1的位置减R的值，R位置的值增加了K，那当前的值减去增加 k 之后的值，它们的差值对比之前一定是减少了k，所以如果在a数组L到R之间的区域统一加了一个k的话，相当于是在差分数组里面仅需让L的位置加一个k，R+1的位置减少一个k，就可以还原出原始数组更改的情况了，这个性质就是根据差分数组的定义出来的，带着这个性质，在L到R区域里面，f [ L ] += k , f [ R+1 ] -= k，就可以实现修改操作了

有的时候大家会看到别的地方解决这个问题的时候，并没有用这个公式，创建差分数组的时候，第一种方式是利用定义来创建，也就是有当前值减去前面的值就可以了，在预处理查分数组的时候，还有另外一种方式，利用性质创建差分数组，这是用的最多的情况，如果此时读到 a [ i ] 这个值，相较于差分数组而言，相当于是在原始第 i 个位置加上了 a [ i ] 这个数，当我读到 a [ i ] 这个数的时候，相当于之前原始数组 i 这个位置是 0 ，当我读完 a [ i ] 之后，相当于第 i 个位置多了一个 a [ i ] ，所以在差分数组这里，直接在 f [ i ] 这个位置加等上一个 a [ i ] ，在 f [ i + 1 ] 的位置减等上一个 a [ i ] ，相当于第 i 个位置多了一个 a [ i ] 这个数，这就是利用差分数组的性质，所以我们创建差分数组的时候有两种方式，第一种方式直接用a [ i ] - a [ i ] - 1，第二种直接利用差分数组的性质，用 f [ i ] += a [ i ] , f [ i + 1 ] -= a [ i ] ，利用性质来创建查分数组，就不用再创建原始数组了，因为读完当前这个位置的值的时候直接把 f [ i ] 修改了；

两种方法得到的是一样的结果，只不过它们的区别就在于第一种方法，在遍历到 i 位置的时候才处理 i 位置的差值；第二种方法是在遍历到 i 位置的时候，顺便提前把 i + 1 位置减去当前位置输入的值，因为 i + 1 位置早晚都要减去它前一个位置的值，提前把它处理了，还不用再开辟一个原始数组a；第二种就是利用差分的性质，把 i 下标看出L到R的区域，输入的值就是K，此时 f [ i ] += k, f [ i + 1 ] -= k；

3.如何还原出原始的数组?

• 直接对差分数组做前缀和运算即可

根据上面的推导过程，此时 a [ i ] 不就是一个前缀和嘛，从1到 i 这个区间里面所有元素的和，就相当于对 f 这个数组做前缀和，做完前缀和之后，每一个元素对应的就是a1、a2、a3…，所以对 f 这个数组做一下前缀和就可以还原出原始的数组

代码：

利用差分定义：

#include <iostream>
using namespace std;

typedef long long LL;
const int N = 1e5 + 10;
LL a[N];
LL f[N];
int n, m;	

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; ++i)
	{
		cin >> a[i];
		f[i] = a[i] - a[i - 1];
	}

	while (m--)
	{
		LL l, r, k; cin >> l >> r >> k;
		f[l] += k, f[r+1] -= k;
	}

	for (int i = 1; i <= n; ++i)
	{
		a[i] = a[i - 1] + f[i];
		cout << a[i] << ' ';
	}

	return 0;
}

利用差分性质：

#include <iostream>
using namespace std;

typedef long long LL;
const int N = 1e5 + 10;
LL f[N];
int n, m;

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; ++i)
	{
		int x;  cin >> x;
		f[i] += x;
		f[i + 1] -= x;
	}

	while (m--)
	{
		LL l, r, k; cin >> l >> r >> k;
		f[l] += k, f[r + 1] -= k;
	}

	for (int i = 1; i <= n; ++i)
	{
		f[i] = f[i - 1] + f[i];
		cout << f[i] << ' ';
	}

	return 0;
}

注意事项：

差分数组使用的时候，就是修改某一个区间，让某一个区间里的所有元素统一加上某一个数的操作，必须是让这种所有的操作全部进行完毕之后，才能还原出操作之后的数组，因为我们要还原出操作之后的数组，必须要来一个前缀和运算才行，它的时间复杂度是O（N）级别，如果这道题它是这样来询问的：每操作若干次就查询一个操作之后的结果，然后会继续操作，继续查询；后面我们会遇到有些题目依旧是把区间某一段元素全都加上一个值，但这种题目考察的时候，它是每一次操作完这个操作之后，它就会询问你操作完之后某一个位置的值是多少，它会继续执行这个操作，继续让某一个区间再加上一个数，然后继续查询，它的操作跟查询是穿插在一起进行的，此时用差分数组就不行了，因为这个差分数组相还原原来的数组要做一个前缀和，前缀合的时间复杂度是O（N）级别，如果有道题它是操作完再查询，操作完之后再查询，此时这个差分数组的时间复杂度是特别高的，解决这个问题就要用后面会谈到的线段树，以后我们再来讨论