前缀和

前缀和是指某序列的前n项和，可以把它理解为数学上的数列的前n项和

作用：一种预处理，求出的前缀和数组可以使得，输出原序列中从第l个数到第r个数和的时间复杂度变成了O(1) 。

一维前缀和

更实际的应用：利用前缀和数组我们可以得到第i项到第j项的和，比如：求原数列第4项到第9项的和。利用前缀和数组: S=sum[9]-sum[4-1]。

const int N=1e5+10;

int sum[N],a[N];

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

{

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

}

第一节课——dfs、bfs、二分、尺取、前缀和、差分 - Virtual Judge (csgrandeur.cn)

#include <iostream>

using namespace std;

const int N = 1000;

long long a[N], sum[N];

int main()

{

	int n, q;

	cin >> n >> q;

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

	{

		cin >> a[i];

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

	}

	while (q--)

	{

		int f, t;

		cin >> f >> t;

		cout << sum[t] - sum[f - 1] << endl;

	}

}

二维前缀和

sum[ i ] [ j ] = sum[ i ] [ j - 1 ] + sum[ i - 1 ] [ j ] - sum[ i - 1 ] [ j - 1 ] + a[ i ] [ j ]

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

        for (int j = 1; j <= m; ++j)

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

更实际的应用:求a[ x1 ] [ y1 ]到a[ x2 ][ y2 ]

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

子矩阵求和

给出一个 n 行 m 列的矩阵，矩阵的每个位置有一个非负整数 a[ i ][ j ]，有 q 次询问，每次询问求一个左上角为 (a,b)，右下角为 (c,d) 的子矩阵的所有数之和。

输入格式

第一行两个整数 n,m，表示矩阵的行和列的大小。

接下来 n 行每行 m 个整数，为矩阵内容。

接下来一行为一个整数 q ，表示询问次数。

接下来 q 行每行 4 个整数 a,b,c,d,含义见题面。

输出格式

共 q 行，第 i 行为第 i 个询问的答案。

样例输入复制

样例输出复制

#include<iostream>

#include<vector>

using namespace std;

int n, m;

int s[1000][1000], sum[1000][1000];

int main()

{

	int i, j, q, a, b, c, d;

	cin >> n >> m;

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

		for (j = 1; j <= m; j++)

			cin >> s[i][j];

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

		for (j = 1; j <= m; j++)

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

	cin >> q;

	while (q--)

	{

		cin >> a >> b >> c >> d;

		cout << sum[c][d] + sum[a - 1][b - 1] - sum[a - 1][c] - sum[c][b - 1] << endl;

	}

	return 0;

}

巴特西

【ACM程序设计】前缀和

前缀和

一维前缀和

二维前缀和

子矩阵求和

最新文章

热门文章