差分数组
差分数组
前面学习了前缀和,根据前缀和的定义,我们可以知道如下等式:
对于数组,有
则s数组便为a数组的前缀和数组。
<view>
那么差分的定义又是什么呢?
对于数组,有</view>
则d数组便为a数组的差分数组。
差分数组的理解
我们可以根据式子知道,差分数组d中每一个值,代表的是a数组当前位置的元素与前一元素相减的结果,即相邻两数的差距。
下面用例题来讲一讲吧。
NOIP2013积木大赛
这一题仔细想想,如果需要另外在一段连续区间[l,r]中搭建积木的话,说明这一区间的长度是大于这个区间外的相邻两个积木的高度的。那么我们只需要关注差分数组,从前往后扫一遍差分数组,如果差分数组是正数,那就说明这个位置能够一起搭建的积木高度已经停了,下一个位置的积木需要在另一个区间里慢慢叠高。如果差分数组是负数,说明它比它的前一个要小,它可以和前一个积木先叠到和它一样的高度,然后再等前一个积木慢慢叠到它的高度。这样子就不用重复再另外叠它了。
代码:
#include <iostream> #include <stdio.h> #include <cstdio> #include <stdlib.h> #include <string> #include <string.h> #include <cstring> #include <math.h> #include <cmath> #include <queue> #include <stack> #include <vector> #include <map> #include <algorithm> #define _for(i,a,b) for(int i=(a) ;i<=(b) ;i++) #define _rep(i,a,b) for(int i=(a) ;i>=(b) ;i--) #define mst(v,s) memset(v,s,sizeof(v)) #define IOS ios::sync_with_stdio(false) #define ll long long #define INF 0x7f7f7f7f7f7f7f7f #define inf 0x7f7f7f7f using namespace std; const int N=100005; int n,t; int a[N]; int c[N]; ll ans=0; void ready() { IOS; cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) c[i]=a[i]-a[i-1]; } void work() { for(int i=1;i<=n;i++) if(c[i]>0) ans+=c[i]; cout<<ans; } int main() { ready(); work(); return 0; }
NOIP2018
这一题和上一题的理解一样,代码也是一样。如果这道题改一改,di都是小于0的话大家要反过来考虑噢。
差分数组的运用
利用高阶差分,我们可以找到一个很明显的应用。
假设一段数组为0 0 1 1 1 1 1 ……
我们可以算出,它的差分数组为0 0 1 0 0 0 0 ……
通过比对两个数组可以发现,在差分数组中的1,会对后面的所有元数都有影响,也就是这个1使得后面的元素都为1了。
那么我们就可以想,如果想让一个数组后面的所有数全部都加1的话,那么就可以在这个数的差分数组操作,最后作一个前缀和就是原数组了。
那么如果要修改一个区间,该怎么办呢?
在差分数组+1,也就是让这个区间后续的数全都有一个+1的影响。如果为了消除这种影响,那么在这个区间的结束位置之后全部-1就能抵消掉这个区间外的影响了。
例如:如果原数组为0 0 1 1 1 1 0 0,那么化为差分数组为0 0 1 0 0 0 -1 0,也就是在那段区间外第一个元素的差分数组-1即可抵消。
看一个例题吧
小w的糖果
对于这道题,有3个操作:
- 选一个位置开始,依次向右每个人发1个糖果
- 选一个位置,依次向右发1,2,3,4……个糖果
- 选一个位置,依次向右发1,4,9,16……个糖果
我们考虑用差分数组,对于第一个操作,后续的数组全部加1,假设一个数组为全1,也就是数组为1 1 1 1……,那么它的差分数组即为1 0 0 0……,在这道题,只需要在开始位置的一阶差分数组+1,即可。
对于第二个操作,我们思考数组1,2,3,4……,让它做一次差分之后,一阶差分数组为1,1,1,1……,似乎没什么规律,那我们再多做一阶呢?也就是做原数组的二阶差分,得到的差分数组为1,0,0,0……,那么规律就显而易见了,我们可以在它的二阶差分数组之中+1,这样子再做回两次前缀和就行。
那么对于第三个操作,我们也将它作差分数组,原数组为1,4,9,16……,那么做一次差分之后,得到的数组为1,3,5,7……,再做一次差分数组,得到1,2,2,2……,如果再做一遍,就能得到1,1,0,0……。我们可以得到,在它的三阶差分时,化为了一段连续有限的序列,这样子只需要在它的三阶差分数组进行操作即可。
代码:#include <iostream> #include <stdio.h> #include <cstdio> #include <stdlib.h> #include <string> #include <string.h> #include <cstring> #include <math.h> #include <cmath> #include <queue> #include <stack> #include <vector> #include <map> #include <algorithm> #define _for(i,a,b) for(int i=(a) ;i<=(b) ;i++) #define _rep(i,a,b) for(int i=(a) ;i>=(b) ;i--) #define mst(v,s) memset(v,s,sizeof(v)) #define IOS ios::sync_with_stdio(false) #define ll long long #define INF 0x7f7f7f7f7f7f7f7f #define inf 0x7f7f7f7f using namespace std; const int N=1e5+5; const int mod=1e9+7; int n,T,m; int dp[4][N]; void ready() { scanf("%d",&T); return ; } void work() { mst(dp,0); scanf("%d%d",&n,&m); while(m--) { int t,s; scanf("%d%d",&t,&s); if(t==1) dp[1][s]++,dp[1][s]%=mod; if(t==2) dp[2][s]++,dp[2][s]%=mod; if(t==3) dp[3][s]++,dp[3][s+1]++,dp[3][s]%=mod,dp[3][s+1]%=mod; } for(int i=2;i>=0;i--) { for(int j=1;j<=n;j++) { dp[i+1][j]=(dp[i+1][j]%mod+dp[i+1][j-1]%mod)%mod; dp[i][j]+=dp[i+1][j]; } } for(int i=1;i<=n;i++) printf("%d ",dp[0][i]%mod); printf("\n"); return ; } int main() { ready(); while(T--) work(); return 0; }
例题:
智乃酱的静态数组维护问题多项式
这一题就是一个区间修改的一般性问题,这里直接写出结论了。对于一个k次多项式,只需要做k+1阶差分,就能够使得一段连续无限的区间化简成一段有限的区间。
代码里面做差分的区间长度为10,是为了更好地找到差分之中的规律。如果数组后面为0,那么其实对于差分也是没有影响。
代码:(还没有调好,先不放了)
牛牛的Link Power I
这道题给出一个01串,其实就是想让我们找出每一个1对后面的影响。
对于一个100101,对于第一个1,它到后面第一个1的距离为3,也就是影响是3,它到第二个1的距离为5。如果只看第一个数,它先往后挪一个位置,再做两次前缀和,可以看出其数组为012345,对应的1的位置便是它对于后面的影响。
同理,如果要求第二个1对后面的1的影响,也是做前缀和就行。
那么对于这个01串,将每一个1往后挪动一位,然后做两次前缀和,如果有一个位置上位1,那么这个前缀和数组里的值便是它前面的1对它的影响。
代码:
#include <iostream> #include <stdio.h> #include <cstdio> #include <stdlib.h> #include <string> #include <string.h> #include <cstring> #include <math.h> #include <cmath> #include <queue> #include <stack> #include <vector> #include <map> #include <algorithm> #define _for(i,a,b) for(int i=(a) ;i<=(b) ;i++) #define _rep(i,a,b) for(int i=(a) ;i>=(b) ;i--) #define mst(v,s) memset(v,s,sizeof(v)) #define IOS ios::sync_with_stdio(false) #define ll long long #define INF 0x7f7f7f7f7f7f7f7f #define inf 0x7f7f7f7f using namespace std; const int mod=1e9+7; const int N=1e5+5; int n,T,ans; int sum[N]; char c[N]; void do_it() { for(int i=1;i<=n;i++) sum[i]+=sum[i-1],sum[i]=sum[i]%mod; } void ready() { IOS; cin>>n; cin>>c+1; for(int i=1;i<=n;i++) if(c[i]=='1') sum[i+1]=1; } void work() { do_it(); do_it(); for(int i=1;i<=n;i++) if(c[i]=='1') ans=(ans%mod+sum[i]%mod)%mod; cout<<ans; } int main() { ready(); work(); return 0; }
本专栏为数据结构专题班的笔记(作业),当然也可以在整理后作为一个学习资料使用