1. 差分算法概述

差分可以简单的看成序列中每个元素与其前一个元素的差。

差分算法和 前缀和算法是有一定关系的。前缀和序列的第 i 项是序列中前面 i 个数之和，我们通过 ${sum}_r - sum_{l-1}$ 可以得到原数组 $a_l + a_{l+1} + ... + a_{r}$ , 极端的情况下，l=r，那么 ${sum}_r - sum_{l-1}$ = ${sum}_r - sum_{r-1}$ = $a_r$ ，这个公式就可以用前缀和数列来反求出原数列的某一项。

而差分算法先求出序列项之间的差值，进而反推出序列原有值的方法，这差分算法的核心内容，同时也是差分算法在解题过程中的运用方向。

原数列是 $a_1 , a_2 , ... a_n$ ，那么我们可以得到它的差分数列是：

$a_1-0 , a_2-a_1 , ... a_n-a_{n-1}$ , 为了方便描述，我们称这个差分数列为 dif 数列（difference 是差的意思），$diff_1 , diff_2 , ... , diff_n$

只要我们手中有正确的 dif 数列，我们就可以求出原数列。

$a_1$ = $diff_1$ + 0 = $diff_1$ -->我们先求出了 $a_1$

$a_2$ = $diff_1$ + $a_1$ --> 我们用 $diff_1$ 和刚刚求出的 $a_1$ 求出了 $a_2$

$a_2$ = $diff_2$ + $a_2$ --> 我们用 $diff_2$ 和刚刚求出的 $a_2$ 求出了 $a_3$

2. 例题

题目描述

在一个桌子上摆放了 n 个杯子，最开始的时候，每个杯子都是空的。小 A 同学负责向杯子中倒水，他总共倒了 k 次，每次会向从第 L 个杯子到第 R 个杯子中添加 P 毫升的水（注意：水只可能增加，不可能减少）。
请问小 A 同学倒了 k 次水之后，n 个杯子每个杯子有多少毫升的水。

输入格式

第一行包含两个整数 n 和 k 。

接下来k行，每行包含三个整数L，R，P，表示一次操作。

数据范围

1 ≤ n , k ≤ 100000

1 ≤ L ≤ R ≤ n

0 ≤ P ≤ 1000

0 ≤ 杯子中水的初始量 ≤ 1000

本题数据上保证所有的杯子在加水之后，水量值任然在 int 范围内。

输出格式

共一行，包含 n 个整数，表示最终 n 个杯子每个杯子有多少毫升的水。

样例

8 7
1 3 1
3 6 2
6 8 1
2 7 1
1 8 3
4 5 1
2 2 2

4 7 7 7 7 7 5 4

笨方法

学好方法之前，我们先看看传统方法怎么解题，无非就是老老实实的给每一个杯子倒水了。所以，这是一个两层循环的程序。外层循环是 k 循环，有多少次操作就循环多少次；内层循环是循环每一个被影响到的杯子，修改杯子里的水量。

#include<bits/stdc++.h>
using namespace std;
int x[100001];
int main()
{
	int i,j,n,k,l,r,p;
	scanf("%d%d",&n,&k);
	while(k--)
	{
		scanf("%d%d%d",&l,&r,&p);
		
		for(j=;j<=r;j++)
			x[j] += p;
	}
	
	for(i=1;i<=n;i++)
		printf("%d ",x[i]);

	return 0;
}

这个代码很容易理解，也很容易写，大多数时候，能写出这个代码应该能拿到 40 到 60 分，至于具体多少分，就看出题人手狠不狠了。

这个代码最大的问题是 计算复杂度 太大了。假设做了 100000 次倒水操作，每次都是都第 1 杯 加到第 100000 杯，那么这个双层循环就是相当于循环了 ${10}^{10}$ ， 这一定超时的。可能有些小朋友觉得这样子来弄数据讲武德，但是，规则就是规则，这样弄数据并没有违反题目说的数据规模，符合规则的数据就是合法数据，出题人就是这样子挖坑的。如果搞不定这样的数据，那只能说你学艺不精。

如果出题老师心情不好，他觉得这个简单的算法就是应该会的，他把当中 60 分的数据弄得很大规模，那你就只能得到 40 分了。蓝桥杯的数据比较 “水” ， 一般来说只要你写得出上面的这种代码，也能拿满分，或者 80 分了。所以，人家说 “蓝桥杯=暴力倍”，如果是南海区的竞赛，这条题估计会放在第 3 题或者第 4 题，用上面的暴力算法，估计能拿 40~60 分。

浅浅介绍了测试数据的设计、老师挖坑，大家平常做题，应该留意题目交待的数据范围，甄别出哪里有坑。当你能识别出坑，你才有可能在掉进坑之前跳过这个坑。考试的时候，提交了代码，是看不到分数的，你掉进了坑里是不知道的。识别坑的能力尤其重要。

计算过程图解
我们用一系列的图表来记录着每一次倒水操作，观察操作完之后水量情况以及差分数组的变化。

1. 初始状态

横坐标是杯子，纵坐标是杯子里的水量。题目说只有 8 个杯子，但是，我却画出了 10 个杯子（从 0 到 9），则是有原因的。原因是什么，后面再说，现在先不讨论。反正，你就假设在两端多放个杯子，你也不会往 0 号和 9 号杯子里面倒水的，多放杯子不影响结果的。

2. 第一次操作，往 1,2,3 号杯子倒水，每个杯子加 1 。

加了水，杯子里就有水了，为了方便理解，同一次加的水颜色一样。

大家要特别留意图下方的“差分数组的值”。我们定义 $diff_i$ = $a_i$ - $a_{i-1}$ ，我们就是假设杯子里的水（$a_i$$）是用笨方法算出来的，然后，我们又用笨方法根据$a_i$算出了差分数组$diff_i$ 。

3. 第二次操作，往 3, 4 , 5 , 6 号杯子里倒水，每杯水加 2 。

4. 第三次操作，往 6 , 7 , 8 号杯子里倒水，每杯水加 1 。

5. 第四次操作，往 2 到 7 号杯子里倒水，每杯水加 1 。

6. 第五次操作，往 1 到 8 号杯子里倒水，每杯水加 3 。

7. 第六次操作，往 4 、 5 号杯子里倒水，每杯水加 1 。

8. 第七次操作，往 2 号杯子里倒水，加 2 。

3. 总结规律

我们发现，给第 l 到第 r 个杯子加水，每杯水加 p ，diff 数组的变化规律是 diff[l] += p , diff[r+1] -= p，而在这个公式里面，diff数组是需要访问到了 r+1，所以，我们定义 diff 数组的时候要定义大一点点，这也就是为什么上面的图例里面要画 9 个杯子的原因。

上面的这个结论是整个差分算法的核心，有了这个公式，意味着我们在每次给一堆水杯倒水的时候，不需要通过一个循环语句来加水，而只需要 2 个语句就可以记录了这个倒水操作（如果 r 比 l 大很多很多的时候，这个效率差异会很明显）。

最后，我们通过 $a_i$ = $a_{i-1}$ + $diff_i$，可以还原出从 1 到 n 号杯子最终的水量，因为公式里面用到 $a_{i-1}$，所以上面的图我故意把 0 号杯子画出来。

4. 程序填空

#include<bits/stdc++.h>
using namespace std;
int x[100001],diff[填空(1)];
int main()
{
	int i,n,k,l,r,p;
	scanf("%d%d",&n,&k);
	while(k--)
	{
		scanf("%d%d%d",&l,&r,&p);
		
		diff[l] += 填空(2);
		diff[填空(3)] -= 填空(4);
	}
	
	for(i=1;i<=n;i++)
	{
		x[i] = 填空(5);
		printf("%d ",x[i]);
	}

	return 0;
}

填空(1):{{ input(1) }}

填空(2):{{ input(2) }}

填空(3):{{ input(3) }}

填空(4):{{ input(4) }}

填空(5):{{ input(5) }}