一维前缀和和差分


  • 一维前缀和

   因为有i-1所以下标要从1开始存

    int n=1010,a[maxn]={0},sum[maxn]={0};
    //sum[]为前缀和数组
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];//也可以直接在原数组上求前缀和 a[i]=a[i]+a[i-1]
    }
  • 一维差分

 1.求【l,r】区间内所有元素的和?

    int ans,r,l;
    ans=sum[r]-sum[l-1];

 2.求数组中连续一段数的和,绝对值最小?

     思路:对前缀和的绝对值排序,求最小的

 3.把一个数组从中间p位置分开,使得a[0]+…+a[p-1]与a[p]+a[p+1]+…+a[n-1]差值最小?

     思路:前一部分A,后一部分B,整个数组的和all。

     要使A-B=A-(all-A)=2*A-all最小,那么就要使2*A最接近all,

4. 两种操作格式:op L R X 。op=1,让区间[L,R]内的元素都减少X;op=0,让区间[L,R]内的元素都增加X,最后再给出一个区间(l,r),求该区间内所有元素的和?

    思路:暴力很可能会超时,用差分做。举个执行单次加或者减例子,试一下就明白原因了。

    int b[maxn]={0},sum={0},add=0;
    if(op==1)//都减少
    {
        b[L]-=x;
        b[R+1]+=x;
    }
    if(op==0)//都增加
    {
        b[L]+=x;
        b[R+1]=-=x;
    }
    for(int i=1;i<=n;i++)
    {
        add+=b[i];
        sum[i]=sum[i-1]+a[i]+add;
    }
    cout<<sum[r]-sum[l-1]<<endl;

二维前缀和和二维差分


  • 二维前缀和

   i和j都要从1开始

    //n*m大小的二维数组
    int a[maxn][maxn],sum[maxn][maxn]={0};
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j];
            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
        }
    }
  • 二维差分

  参考博客https://blog.csdn.net/k_r_forever/article/details/81775899

 1.求A(x1,y1)和B(x2,y2)所围成的矩形内所有元素的和,A在B的左上方

    int x1,y1,x2,y2,ans;
    ans=sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][y1-1];//实在记不住就举个简单的例子试试

模版题:https://blog.csdn.net/Cassie_zkq/article/details/88667948

2.和一维差分的第四个问题类似,让(x1,y1)和(x2,y2)矩形内的数都加x(应该是+吧,我觉得,看其他博主的博客都没有讲这是在加还是减,我暂且推测是加,欢迎纠错,目前还没有找到例题)

    int b[maxn][maxn]={0},x1,y1,x2,y2;
    if(op==1)//加上一个数
    {
        b[x1][y1]+=x; b[x2+1][y2+1]+=x;
        b[x1][y2+1]-=x; b[x2+1][y1]-=x;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            //暂时不会写了(捂脸),要不举个例子试一下emmm,请大佬赐教
        }
    }

树上差分(待学)