1.定义：
对于离线数列d，建立差分数组f，则 f[1]=d[1],f[i]=d[i]-d[i-1]
2.性质
(1):对于各个项，有d[2]=d[1]+ (d[1]-d[1]) =f[1]+f[2],即：d[i]=Σf[i]
(2):求数列的前缀和 sum(x)=Σ(i=1,x)Σ(j=1,i)f [ j ]=Σ(i=1,x)(x-i+1)*f(i)
3.作用
快速处理区间加减操作，对[L,R]的数都加上x，则f[L]+=x,f[R+1]-=x;
询问区间和问题，[L,R]的值 ans=sum[R]-sum[L-1];
例题：http://acm.hdu.edu.cn/showproblem.php?pid=1556
#include <iostream> #include <algorithm> using namespace std; typedef long long ll; const int maxn=1e5+7; int d[maxn],f[maxn]; int main( ) { int n; while(cin>>n) { if(n==0) break; for(int i=1;i<=n;i++) d[i]=0,f[i]=0; for(int i=1;i<=n;i++) { int a,b; cin>>a>>b; f[a]+=1; f[b+1]-=1; } int ans=0; for(int i=1;i<=n;i++) { ans+=f[i]; if(i==n) cout<<ans<<endl; else cout<<ans<<" "; } } return 0; }