算法基础：前缀和

前缀和

一维前缀和

思想：假设有原数组a1，a2，a3….an;

求前缀和si

则si = a1 + a2 + … + ai;

若要求区间[l,r]之间的前缀和，则只需将r的前缀和减去l - 1的前缀和即可

时间复杂度为O（1）；

模板

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <cstdio>

using namespace std;

const int  N = 100010;

int q[N];
int s[N];
int main()
{
	int n,m;
	scanf("%d %d", &n,&m);

	for (int i = 1;i <= n;++i) scanf("%d", &q[i]);
//每项前缀和的初始化
    for (int i = 1;i <= n;++i) s[i] = s[i - 1] + q[i];
//询问每次
	while (m--)
	{
		int l, r;
		scanf("%d %d", &l, &r);
		printf("%d\n", s[r] - s[l-1]);
	}
	return 0;
}

二维前缀和

思想：有一二维数组q，将其看作一个长方形，其二维前缀和s[ i ] [ j ]就是从a[0] [0] 至 a [i] [j] 所有元素的和，

如果想要快速得到每一个s[ i ] [ j ],可以用公式推得

s[i] [j] = s[i - 1] [j] + s[i] [j - 1] - s[i - 1] [j - 1] + a[i] [j];

如果想要求出特定长方形x1，y1至x2，y2的长方形前缀和

则可以利用公式

sum = s[x2] [y2] - s[x1 - 1] [y2] - s[x2] [y1 - 1] + s[x1 - 1] [y1 - 1]

模板

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>

using namespace std;

const int N = 10010;

int q[N][N];
int s[N][N];

int main()
{
	int n, m,k;
	scanf("%d%d%d", &m, &n, &k);
	
	for (int i = 1;i <= m;++i)
	{
		for (int j = 1;j <= n;++j)
			scanf("%d", &q[i][j]);
	}
	//每一项前缀和初始化
	for (int i = 1;i <= m;++i)
		for (int j = 1;j <= n;++j)
			s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i-1][j-1]+q[i][j];
	//询问
	while (k--)
	{
		int x1, y1, x2, 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;
}