前缀和及模板
1. 一维前缀和数组定义及问题引出
假设我们拥有原数组：A = a1,a2,a3,...,an
那么，前缀和数组可以定义为：Si = a1+a2+...+ai(即：原数组中前i个数相加所构成的数组)
根据上述的定义，我们可以引出如下问题：
1. 如何求Si?
2. 前缀和数组的作用？
2. 一维前缀和数组求法及作用
1.如何求Si?
我们可以通过for循环来求解。即：
for i=1; i<=n; i++
s[i] = s[i-1] + ai //Si = Si-1 + ai
需要注意的是，上述解法需要定义边界。即：S0 = 0。
2.前缀和数组的作用？
可以快速求出来原数组中一段数的和。
假如：需要求出原数组中一段数[l,r]的和
1. 如果没有前缀和数组的话，那么需要循环一遍，这样的话时间复杂度就是O(n)。
2. 但是如果有前缀和数组的话，那么只需要通过公式：Sr - Sl-1即可。这样的话，时间复杂度就是O(1)。
解释一下上述的公式：
Sr = a1 + a2 + ... + al-1 + al + ... + ar
Sl-1 = a1 + a2 + ... + al-1
相减即为答案。
注意:
1. 前缀和数组一般从下标1(S1)开始，下标0(S0)一般定义为0。目的是:将上述的公式Sr - Sl-1进行统一。
2. 假设：我要求出[1,10]这一段数的和，正常来讲就是S10。但是，为了采用公式：Sr - Sl-1,我们只能将S0 = 0。即：S10 - S1-1 = S10 - S0 = S10。
3. 一维前缀和模板
S[i] = a[1] + a[2] + ... a[i]
a[l] + ... + a[r] = S[r] - S[l - 1]
4. 一维前缀和例题
https://www.acwing.com/problem/content/797/
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 100010;
int main(){
int q[N];
int S[N];
int n,m;
int l,r;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&q[i]);
}
S[0] = 0;
for(int i=1;i<=n;i++){
S[i] = S[i-1] + q[i];
}
while(m--){
scanf("%d %d",&l,&r);
printf("%d\n",S[r] - S[l-1]);
}
return 0;
}
5. 二维前缀和数组定义及问题引出
假设我们拥有原二维数组：A = a11,a12,a13,...,aij,...,ann。
那么，前缀和数组可以定义为：Sij = a11+a12+...+a1j+...+ai1+ai2+...+aij(即：原二维数组中aij左上角所有元素的和)
根据上述的定义，我们可以引出如下问题：
1. 如何求Sij?
2. 二维前缀和数组的作用？
6. 二维前缀和数组求法及作用
1.如何求Sij?
我们可以通过二重for循环来求解。即：
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
Sij = Si-1j + Sij-1 - Si-1j-1 + aij //推出Sij的公式
2.二维前缀和数组的作用？
可以快速求出来原二维数组指定区域中数的和。
假如：需要求出原二维数组中(x1,y1)和(x2,y2)所围成的区域中数的和。
1. 如果没有二维前缀和数组的话，那么需要二重循环，这样的话时间复杂度就是O(n²)。
2. 但是如果有二维前缀和数组的话，那么只需要通过公式：Sx2y2 - Sx2y1-1 - Sx1-1y2 + Sx1-1y1-1即可。这样的话，时间复杂度就是O(1)。
解释一下上述的公式：
1. Sx2y2是ax2y2左上角元素之和。
2. Sx2y1-1是红色区域之和。
3. Sx1-1y2是绿色区域之和。
4. Sx1-1y1-1是ax1-1y1-1左上角元素之和。
关于前缀和需要注意的是：前缀和算法一般下标从1开始写，比较方便。上图展示了一个具体案例，求(2,2)和(3,3)所围成的区域的和。
7. 二维前缀和模板
S[i, j] = 第i行j列格子左上部分所有元素的和
以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]
8. 二维前缀和例题
https://www.acwing.com/problem/content/798/
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1010;
int main(){
int n,m,q;
int M[N][N];
int S[N][N];
int x1,y1,x2,y2;
scanf("%d %d %d",&n,&m,&q);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf("%d",&M[i][j]);
}
}
//初始化前缀矩阵
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + M[i][j];
}
}
while(q--){
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
printf("%d\n",S[x2][y2] - S[x2][y1-1] - S[x1-1][y2] + S[x1-1][y1-1]); //求出部分和
}
return 0;
}
注意：二维前缀和和一维前缀和的区别就在于：二维前缀和不需要初始化，而一维前缀和需要初始化S[0]。
作者：gao79138
链接：https://www.acwing.com/
来源：本博客中的截图、代码模板及题目地址均来自于Acwing。其余内容均为作者原创。
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。