目录

一 定义：

顾名思义，就是一个数组中相邻的两个数的差值所组成的新数组；

例如：

为了方便表达，我在a数组的最前面多家一个数a[0]=0;实际中的数是从1开始的；

数组 a[n]:    a[1] a[2]  a[3] a[4]...................... a[n];

差分数组d[n]:   d[1]=a[1]-a[0]=a[1]    d[2]=a[2]-a[1]   d[3]=a[3]-a[2]   .............. d[n]=a[n]-a[n-1];

 

 二 性质：

① 假设现在我们知道差分数组，求原数组a[n]。

由d[1]=a[1]-a[0]===>a[1]=d[1]+a[0]=d[1];

d[2]=a[2]-a[1]===>a[2]=d[2]+a[1]=d[2]+d[1]

d[3]=a[3]-a[2]===>a[3]=d[3]+a[2]=d[3]+d[2]+d[1]

................................................................................................

a[n]=d[n]+d[n-1]+............+d[1]

 

②求数组a[n]得前前缀和sum[i]

   

故sum[n]=n*d[1]+(n-1)*d[2]+(n-2)*d[3]+..........+2*d[n-1]+d[n]

也可以这样写：sum[n]=sum[n-1]+d[n]; 这个比较简单，从上面的式子就可以推出，可以自己证明；

③对a数组的[L,R]区间的每个数的加上一个数a。之后差分数组就会发生改变，这个影响从第L个数一直到第（R+1）个数，要解决这个问题。我们就要d[L]+a,  d[R+1]-a;

为什么这样可以呢？从性质①入手，a[L]=d[L]+.....d[1]。当我们在[L,R]这段区间上加上a的时候，从d[1]到d[n]，改变的仅仅是d[L]和d[R+1],[L,R]中的d[i]因为是同时加上一个数，所以他们的差不改变。从而达到修改两个值来维护一段区间的效果。

下面来看一个题目：

http://poj.org/problem?id=3263

思路：我们开始时假设所有牛的高度都想等为0。当我们被告知A和B 可以相互看见时，考虑到题目要求每头牛的身高最可能大，那么就把他们中间的所有牛的身高都减1,那这时候我们就可以再开一个数组，利用上面的差分数组，来维护这些信息了。具体看代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
typedef pair<int, int> p;
const int MAXN = 1e4 + 10;
map < p, bool> mp;
int d[MAXN],c[MAXN];


int main() {
	int n, q, h, m;
	cin >> n >> q >> h >> m;
	int a, b;
	for (int i = 1; i <= m; i++) {
		cin>>a>>b;
		if (a > b)swap(a,b);
		if (mp[make_pair(a, b)])continue;
		d[a + 1]--; d[b]++;
		mp[make_pair(a, b)] = true;
	}

	for (int i = 1; i <= n; i++) {
		 c[i] = c[i - 1] + d[i];
		 printf("%d\n",c[i]+h);
	}

	return 0;
}

 

    再看一道题目：

http://acm.hdu.edu.cn/showproblem.php?pid=1556

这题每上面说的，直接套公式就ok了，代码如下：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<map>
using namespace std;
typedef pair<int, int> p;
const int MAXN = 1e5 + 10;
int n;
map < p, bool> mp;
int d[MAXN],c[MAXN];


int main() {
	while (cin >> n && n) {
		memset(d,0,sizeof(d));
		memset(c,0,sizeof(c));
		int a, b;
		for (int i = 1; i <= n; i++) {
			cin >> a >> b;
			d[a]++; d[b + 1]--;
		}

		for (int i = 1; i <= n; i++) {
			c[i] = c[i - 1] + d[i];
			printf("%d%c", c[i],i==n?'\n':' ');
		}
	}
	return 0;
}