差分数组
目录
顾名思义,就是一个数组中相邻的两个数的差值所组成的新数组;
例如:
为了方便表达,我在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;
}