asatmda

前缀和,差分
什么是前缀和?如果有一段长度为N的序列a[0:N-1],然后给你m的询问,每次询问给出一个区间[L,R],要求你求...
扫描右侧二维码阅读全文
03
2019/10

前缀和,差分

什么是前缀和?

如果有一段长度为N的序列a[0:N-1],然后给你m的询问,每次询问给出一个区间[L,R],要求你求出区间内的和,请问你会怎么做?

  1. 暴力做法(时间复杂度为O(n*m))

每次都遍历一遍它给的区间,计算出答案,这样子的方法固然没错,但是其时间复杂度达到了O(n*m),如果数据量稍微大一点(1e5)就有可能超时

  1. 前缀和(时间复杂度O(n+m))
a[0]=0;
for(int i=1;i<=n;i++)
    a[i]+=a[i-1];

前缀和也就是前面i个数的总和。数组a在经过这样的操作之后,对于每次的询问,我们只需要计算a[R]-a[L-1]就能得到我们想要的答案了。时间复杂度为O(n+m)。

小试牛刀

前缀异或
输入一个长度为n(1 <= n <= 100000)数组a[1], a[2], ..., a[n]。
输入一个询问数m(1 <= m <= 100000)和m组询问,每组询问形如(l, r)
对于每组询问(l, r),你需要输出a[l] xor a[l + 1] xor ... xor a[r - 1] xor a[r],即第l个数字到第r个数字的异或。
如果你的算法需要约n*m的时间,你将只能通过第一个测试点。
如果你的算法需要约n+m的时间,你将可以通过本题。
代码如下:

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
typedef long long ll;
ll a[maxn],b[maxn];
int main(){
    int n,m,l,r;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        b[i]=b[i-1]^a[i];
    }
    cin>>m;
    for(int i=1;i<=m;i++){
        scanf("%d%d",&l,&r);
        printf("%lld\n",b[r]^b[l-1]);
    }
    return 0;
}

什么是差分?

如果有一段长度为N的序列a[0:N-1],要求对a[L]~a[R]进行m次操作:
操作一:将a[L]~a[R]内的元素都加上P
操作二:将a[L]~a[R]内的元素都减去P
最后再给出一个询问求s[L]-s[R]内的元素之和?

  1. 暴力(时间复杂度O(n*m))

对于m次操作每次都遍历一遍a[L]~a[R],给区间里的数都加上P或减去P,最后再求一次前缀和就行了。没错,这样子确实也能得出正确答案,但时间复杂度却高达O(M*n),对于1<=n,m<=1e5这个数据范围来说直接就tle

  1. 差分(时间复杂度O(n))

我们新开一个数组b,储存每一次的修改操作,最后求前缀和的时候统计一下就能快速的得到正确答案了,详细请看下面代码

#include<bits/stdc++.h>

using namespace std;

const int maxn=1e5+9;

int a[maxn],b[maxn];

int main(){

int i,j,k,n,m,p;

cin>>n>>m;

for(i=1;i<=n;i++){

cin>>a[i];

}

for(i=1;i<=m;i++){

int L,R,t;

cin>>t>>L>>R>>p;

if(t==1){

b[L]+=p;b[R+1]-=p; 

}

else{

b[L]-=p;b[R+1]+=p;

}

}

int add=0;

for(i=1;i<=n;i++){

add+=b[i];

a[i]+=a[i-1]+add;

}

int x,y;

cin>>x>>y;

cout<<a[y]-a[x-1]<<endl;

}

Last modification:October 13th, 2019 at 07:02 pm
如果觉得我的文章对你有用,请随意赞赏

One comment

  1. 风情万种

    还有二维前缀和。。。。。。。。。

Leave a Comment