差分数组

差分数组


前面学习了前缀和,根据前缀和的定义,我们可以知道如下等式:
对于数组,有


则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;
}
数据结构笔记 文章被收录于专栏

本专栏为数据结构专题班的笔记(作业),当然也可以在整理后作为一个学习资料使用

全部评论

相关推荐

评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务