【差分数组】

差分数组不仅仅是一个优秀的线性结构，还是一种很好的思想，其主要用于修改区间、查询单点，其中，修改区间的时间复杂度均为 O(1)，查询单点的时间复杂度为 O(n)

对于已知有 n 个元素的离线数列 a，可以建立一个记录它每项与前一项差值的差分数组 f[]，那么显然有：

• f[1]=a[1]-0=a[1]
• f[i]=a[i]-a[i-1]

计算数列各项的值，可以发现：

• a[2]=f[1]+f[2]=a[1]+(a[2]-a[1])=a[2]
• a[3]=f[1]+f[2]+f[3]=a[1]+(a[2]-a[1])+(a[3]-a[2])=a[3]
• a[4]=f[1]+f[2]+f[3]+f[4]=a[1]+(a[2]-a[1])+(a[3]-a[2])+(a[4]-a[3])=a[4]
• ...

以此类推，可以发现数列 a 的第 i 项是可以用差分数组前 i 项和来计算的，即：a[i]=f[i] 的前缀和

计算数量每一项的前缀和，那么有：

即：可用差分数组来求出数列的前缀和

int a[N]; int f[N],sum[N]; void init(){f[1]=a[1];for(int i=2;i<=n;i++)//差分数组f[i]=a[i]-a[i-1];for(int i=1;i<=n;i++)//前缀和sum[i]=sum[i-1]+a[i]; }

【差分数组用途】

1.快速处理区间加减

假如现在要对数列区间 [L,R] 上的每个数都加上 x，那么通过 a[i]=f[i] 的前缀和 的性质可以知道：

• 第一个受影响的差分数组中的元素为 f[L]，所以令 f[L]+=x，那么后面数列元素在计算过程中都会加上 x
• 最后一个受影响的差分数组中的元素为 f[R]，所以令 f[R+1]-=x，那么可以保证不会影响到 R 以后数列元素的计算

这样一来，就不必对区间内每一个数进行处理，只需处理两个差分后的数即可

void add(int L,int R,int x){f[L]+=x;f[R+1]-=x; } void sub(int L,int R,int x){f[L]-=x;f[R+1]+=x; }

2.查询单点

根据差分数组的性质，差分数组第 i 项的前缀和即为序列的第 i 项，因此可利用差分数组来计算原序列第 x 个点的值

int query(int x){int sum=0;for(int i=1;i<=x;i++)sum+=f[i];return sum; }

【模版】

int n,m; int a[N]; int f[N],sum[N]; void init(){//求差分数组f[1]=a[1];for(int i=2;i<=n;i++)//差分数组f[i]=a[i]-a[i-1]; } void add(int L,int R,int x){//区间[L,R]全部加上xf[L]+=x;f[R+1]-=x; } void sub(int L,int R,int x){//区间[L,R]全部减去xf[L]-=x;f[R+1]+=x; } void query(int x){//查询序列第i项int sum=0;for(int i=1;i<=x;i++)sum+=f[i];return sum; } int main(){cin>>n>>m;for(int i=1;i<=n;i++)//输入序列cin>>a[i];init();//计算差分数组while(m--){//m个操作char op;cin>>op;if(op=='A'){//加操作int l,r,x;cin>>l>>r>>x;add(l,r,x);}else if(op=='S'){//减操作int l,r,x;cin>>l>>r>>x;sub(l,r,x);}else if(op=='Q'){//查询操作int x;cin>>x;cout<<query(x)<<endl;}}return 0; }

【例题】

Color the ball（HDU-1556）(单点查询)：点击这里

借教室（洛谷-P1083）(差分数组+二分)：点击这里

总结

以上是生活随笔为你收集整理的线性结构 —— 差分数组的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。