前缀和

• 0. 概述
• 1. 一维前缀和
• 2. 二维前缀和

0. 概述

• 因为前缀和这个板子的推导比较简单，因此本博客重点在于知识点归纳而不在于证明

1. 一维前缀和

• 一维数组的前缀和计算公式：$s[i]=\sum_{i=1}^ia[i]=s[i-1]+a[i]$，时间复杂度 $O(n)$
• 原数组 $[l,r]$ 区间和计算公式：$s[r]-s[l-1]$ ，时间复杂度 $O(1)$

【例题】AcWing 795，链接：795. 前缀和 - AcWing题库

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;

const int N=1e5+5;
int a[N],s[N];

int main() {
	int n;
	int m;
	cin>>n>>m;
	// 输入规模超过1e5时推荐使用scanf而不是cin和cout
	for(int i=1;i<=n;i++) {
		scanf("%d",&a[i]);
	}
	for(int i=1;i<=n;i++) {
		s[i]=s[i-1]+a[i];	
	}
	while(m--) {
		int l,r;
		scanf("%d%d",&l,&r);
		printf("%d\n",s[r]-s[l-1]);
	}
	return 0;
}	

2. 二维前缀和

• 二维数组的前缀和计算公式：$s[i][j]=\sum_{i=1}^i\sum_{j=1}^ja[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j]$，时间复杂度 $O(n^2)$

• 原数组 $(x_1,y_1)$ 到 $(x_2,y_2)$ 区间和计算公式：$s[x_2][y_2]-s[x_1-1][y_2]-s[x_2][y_1-1]+s[x_1-1][x_2-1]$ ，时间复杂度 $O(1)$

【例题】AcWing 796，链接：796. 子矩阵的和 - AcWing题库

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;

// 容斥原理:
const int N=1e3+10;
int n,m,q;
int a[N][N];
int s[N][N]; // 二维前缀和矩阵

int main() {
	cin>>n>>m>>q;
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=m;j++) {
			scanf("%d",&a[i][j]);
			// 预处理二维前缀和数组
			s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
		}
	}
	while(q--) {
		int x1,x2,y1,y2;
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		// 算区间和
		printf("%d\n",s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]);
	}
	return 0;
}

打赏