前缀和的介绍及典型应用"/>
一维、二维差分与前缀和的介绍及典型应用
一维差分与前缀和
定义
对于一维数组a,定义前缀和数组sum:sum[i]=sum[i-1]+a[i],定义差分数组sub[i]=a[i]-a[i-1]。
显然差分与前缀和互为逆运算,原数组a可看成差分数组sub的前缀和,也可看出前缀和数组sum的差分。
前缀和的典型应用
如果已有前缀和数组sum(求sum的时间复杂度为O(n)),那么任意一端连续子数组a[i,j]的和sum(i,j)=sum(j)-sum(i-1)。
差分的典型应用
记a数组长度为n,如果我们想将a数组中连续的一段[i,j]全部加上某个数,重复进行类似加法操作m次,直接操作的时间复杂度为O(mn)。为了降低复杂度,我们可以采用差分数组sub进行辅助。例如,如果我们想将a[i,j]全部加上数字p,可以让sub[i]+=p, sub[j+1]-=p。重复进行类似操作m次,最后重构a数组,时间复杂度O(m+n)。
一维差分例题
题目描述
解题思路
显然本题要用到一维差分数组,来标记原数组某段的增长,最后重构数组,统计最小值即可。
代码实现
#include<bits/stdc++.h>
using namespace std;
int main( )
{// freopen("input.txt","r",stdin);int n,p;cin>>n>>p;vector<int> grade(n+1,0);vector<int> sub(n+2,0);for(int i=1;i<=n;++i){cin>>grade[i];sub[i]=grade[i]-grade[i-1];}int x,y,z;for(int i=0;i<p;++i){cin>>x>>y>>z;sub[x]+=z;sub[y+1]-=z;}int Min=__INT_MAX__;for(int i=1;i<=n;++i){grade[i]=grade[i-1]+sub[i];Min=min(Min,grade[i]);}cout<<Min<<endl;return 0;
}
二维差分与前缀和
定义
对于二维数组a,定义前缀和数组sum:sum[i][j]表示a[i][j]左上部分所有元素的和。显然sum数组有如下递推式:
sum[i][j]=a[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]
则a[i][j]=sum[i][j]+sum[i-1][j-1]-sum[i-1][j]-sum[i][j-1]
根据差分与前缀和的互逆关系(可将sum看成原数组,a看成差分),定义二维差分数组sub的递推式如下:
sub[i][j]=a[i][j]+a[i-1][j-1]-a[i-1][j]-a[i][j-1]
则a[i][j]=sub[i][j]+a[i-1][j]+a[i][j-1]-a[i-1][j-1]
二维前缀和的应用
a数组[i1,i2][j1,j2]部分的和可表示为:
sum[i1,i2][j1,j2]=sum[i2][j2]-sum[i2][j1-1]-sum[i1-1][j2]+sum[i1-1][i2-1]
二维差分的应用
对a数组[i1,i2][j1,j2]部分全部加上数p,可用sub数组表示为:
sub[i1][j1]+=p
sub[i1][j2+1]-=p
sub[i2+1][j1]-=p
sub[i2+1][j2+1]+=p
二维差分典型例题
题目描述
解题思路
用a[i][j]表示第i行第j列覆盖的地毯数,铺放地毯即将对应部分的a[i][j]全部加1,可用sub数组来标记,反复标记,最后重构a数组即可。
代码实现
#include<bits/stdc++.h>
using namespace std;
int main( )
{// freopen("input.txt","r",stdin);int n,m;cin>>n>>m;vector<vector<int>> sub(n+2,vector<int>(n+2,0));vector<vector<int>> num(n+1,vector<int>(n+1,0));int x1,y1,x2,y2;for(int i=0;i<m;++i){scanf("%d%d%d%d",&x1,&y1,&x2,&y2);++sub[x1][y1];--sub[x1][y2+1];--sub[x2+1][y1];++sub[x2+1][y2+1];}for(int i=1;i<=n;++i){for(int j=1;j<=n;++j){num[i][j]=sub[i][j]+num[i-1][j]+num[i][j-1]-num[i-1][j-1];printf(j<n?"%d ":"%d\n",num[i][j]);}}return 0;
}
更多推荐
一维、二维差分与前缀和的介绍及典型应用
发布评论