【模板】差分 题解

引入

我们以这道题目来学习一下差分这个算法。

简化题意

对一个一开始全为 ，长度为 的数组 进行 次操作：

给出 l r x，将 分别加上 。

求操作后的 数组。

解题思路

这题乍一看是暴力对吧？我们每次操作都直接将区域中的每个数加上需要的值，就可以解决此问题了。时间复杂度约为 。

但是，如果 ， 的范围都很大（就比如此题中），我们该如何处理呢？

这里，我们就要引入今天的技巧——差分。

我们给出一个样例：

6 3
2 5 1
1 4 2
3 6 3

暴力操作是这样的：

1. 原序列为 0 0 0 0 0 0。
2. 经过第一次操作，序列变为了 0 1 1 1 1 0。
3. 经过第二次操作，序列变成了 2 3 3 3 1 0。
4. 经过第三次操作，序列变成了 2 3 6 6 4 3。
5. 操作完毕，输出现在的序列。

很明显，暴力操作每次都要更新一次序列，非常麻烦。

那么，我们来看一下差分操作的步骤：

1. 引入一个新数组 ，初始全部值为 。
2. 第一次操作， 数组变为 0 1 0 0 0 -1。
3. 第二次操作， 数组变为 2 1 0 0 -2 -1。
4. 第三次操作， 数组变为 2 1 3 0 -2 -1 (-3)。
5. 然后，我们引入变量 ，初始等于 。遍历数组 ，对于下标 执行 。然后，我们记 。
6. 操作完毕，输出数组 。

我们的操作过程是：

1. c = 2
2. c = 3
3. c = 6
4. c = 6
5. c = 4
6. c = 3

哎？为什么这样操作，得出的也是正确结果呢？像这样操作，我们的时间复杂度就变为了 ，比原来快多了。

这里，我们就要正式开始介绍差分算法了（只是简单的解释）。当我们要进行一次区间加减操作时，设操作的区间为 ，加上的值为 。我们将标记数组的下标 的值加 ，下标 的值减 。

这样，当我们需要求最终的总和时，变量从下标 开始加 ，到了下标 又减 ，在此过程中完成了区间增加的操作。

简单来说，就是我们在完成标记后，从左往右扫描这个标记数组，记录当前经过的标记之和。这个和就是对应那个数的值。

以上部分是自己的思想，可能描述的不太好，大家自行理解，请谅解。

代码部分

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, m;
int flag[500010];
signed main()
{
	cin >> n >> m;
	for(int i = 1, l, r, x;i <= m;i ++)
	{
		cin >> l >> r >> x;
		flag[l] += x, flag[r + 1] -= x;//打下标记 
	}
	int c = 0;
	for(int i = 1;i <= n;i ++)
	{
		c += flag[i];//增加标签大小 
		cout << c << " ";//现在记录的总标记大小即为此位的答案 
	}
	return 0;
}