前缀和

发表于 更新于

前缀和

1.前缀和理解与实现

为什么要用前缀和？
前缀和顾名思义就是前几个数的和，arg[n]即为前n个数的和。这样当我们需要区间(l,r)的和时只需要求prefix[r]-prefix[l-1].
若我们选择遍历大小为n的数组，询问次数为q次。则时间复杂度为O(qn)。
而使用前缀和我们只需要花O(n)遍历数组，再花O(1)求得所需。

前缀和的实现
1.手写
开新的数组

1
2
3
4
5
6
7
vector<int>prefix(n);
for(int i=0;i<n;i++){
    //非起始位置
    if(i)prefix[i]=prefix[i-1]+arg[i];
    //起始位置
    prefix[i]=+arg[i];
}

原数组不用了

1
2
for(int i=0;i<n;i++)
    if(i)arg[i]+=arg[i-1];

2.库函数

1
2
//numeric库
partial_sum(arr.begin(),arr.end(),prefix.begin());

需要注意的点
需要注意下标为0时的数组越界
解决方法：
1.0特判

1
2
3
4
auto sumOf=[&](int l,int r){
    if(l==0)return prefix[r];
    return prefix[r]-prefix[l-1];
}

2.从1开始

1
2
//numeric库
partial_sum(arr.begin(),arr.end(),prefix.begin()+1);

2.前缀和变种

1.前缀积

同理，但是造成了容易溢出的问题。
mul(l,r)=prefix[r]/prefix[l-1]
我们通常会取模，但是这样mul就并不是简单的除法运算，需要用乘法逆元。如费马小定理等。

2.前缀异或和

xor(l,r)=prefix[r]^prefix[l-1]
前缀异或和有一个有趣的性质：有两个前缀相同，则区间的异或和为0。
实现

1
2
3
partial_sum(arr.begin(),arr.end(),xorsum.begin(),[](int prev,int cur){
    return prev^cur;
});

3.二维前缀和

左上角到某地方的前缀和，依据容斥原理
sum(x1,y1,x2,y2)=p[x2][y2]-p[x1][y2]-p[x2][y1]=p[x1][y1]

4.普遍前缀和

我们可以将前缀推广到任意运算，如max,min……但由于没有逆运算，不能求解区间问题。但面对多次查询还是适用的。

2.后缀和

用于求解终点与当前位置的信息。
实现

1
2
3
4
5
6
7
8
9
10
11
    for(int i=n-1;i>=0;i--){
        if(arr[i]){
            if(i!=n-1)suffix[i]=suffix[i+1];
            suffix[i]+=arr[i];
        }
    }
//库函数
    partial_sum(arr.rbegin(),arr.rend(),suffix.rbegin(),[](int prev,int cur){
        if(cur)return prev+cur;
        return cur;
    });