差分

差分适用的问题：

给你一个区间，然后让你对某一个区间加上或者减去一个数，然后询问区间和等问题，可以用差分。

差分就是：除去第一个数外，每一个数减去上一个数。

举个例子：有这样6个数：

原数组	1	6	4	5	3	2
差分后	1	5	-2	1	-2	-1

我们要求原来的数求前缀和就好了。

如果我们要对区间【2,5】加2，只需要让第二个数加2和第6个数减2即可，改变后就是这样：

原数组	1	6	4	5	3	2
差分后	1	5	-2	1	-2	-1
修改后	1	7	-2	1	-2	-3

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
const int maxn = 1e5+10;
int x, y, a[maxn];
int main()
{
	int n;
	while (~scanf ("%d",&n) && n)
	{
		mem(a,0);
		for (int i = 1 ; i <= n ; i++)
		{
			scanf ("%d %d",&x,&y);
			a[x]++; a[y+1]--;
		}
		for (int i = 1; i <= n ; i++)
		{
			a[i] += a[i-1];
			printf ("%d%c",a[i],i==n?'\n':' ');
		}
	}
	return 0;
}

例题：HDU1556用手指戳这里