前缀和及二维前缀和

前缀和

前缀和作用

前缀和主要目的是求子数组的和，如a[3] — a[5]。
a[3]+a[4]+a[5] = S[5] - S[2];

注意

在编码的过程中，要保证我们赋值的下标是从1开始的，可以与数学关联，在数学的数列中下标是从1开始的。不过在循环迭代中会用到下标0的项，因此我们编码过程中需要把下标为0的那一项赋值为0，在c++中默认为0。

一维前缀和

前缀和赋值公式：S[n] = S[n-1] + a[n];
截取某段值公式：a[l] + a[l+1]+ … + a[r] = S[r] - S[l-1];

代码实现

要求：输入一个n代表数组长度，再输入n个对应的整数，最后输入l、r表示要截取的a[l] + a[l + 1] + … + a[r]。

#include <iostream>
using namespace std;const int N = 1010;
int s[N],aN];int main()
{int n;cin >> n;for(int i = 1;i <= n; i++){cin >> a[i];}for(int i = 1;i <= n; i++){s[i] = s[i-1] + a[i];}int l,r;cin >> l >> r;cout << s[r] - s[l-1];return 0;
}

二维前缀和

以子矩阵的和 题为模板来说：
我们用两个数表示行和列，（i，j）是第i行第j列，一定要注意行列说的是单元格，下图中实则是每个单元格存储一个数。

S[i,j] (前缀和)即为图1红框中所有数的和：S[i,j]=S[i,j−1]+S[i−1,j]−S[i−1,j−1]+a[i,j]

左上角(x1,y1)到右下角(x2,y2)的这一子矩阵中的所有数之和为：S[x2,y2]−S[x1−1,y2]−S[x2,y1−1]+S[x1−1,y1−1]

代码实现

题目要求：

输入一个 n 行 m 列的整数矩阵，再输入 q 个询问，每个询问包含四个整数
x1,y1,x2,y2，表示一个子矩阵的左上角坐标和右下角坐标。
对于每个询问输出子矩阵中所有数的和。

输入格式：

第一行包含三个整数 n，m，q。
接下来 n 行，每行包含 m 个整数，表示整数矩阵。
接下来 q 行，每行包含四个整数 x1,y1,x2,y2，表示一组询问。

输出格式

共 q 行，每行输出一个询问的结果。

#include <iostream>using namespace std;const int N = 1010;
int s[N][N],a[N][N];
int main()
{int n,m,q;cin >> n >> m >> q;//输入for(int i = 1;i <= n;i++){for(int j = 1;j <= m;j++)cin >> a[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] + a[i][j];}}int x1,y1,x2,y2;while(q--){cin >> x1 >> y1 >> x2 >> y2;cout << s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1] << endl;}return 0;
}

【2021年8月25日，今天是疫情延迟大一报到的第三天，冲冲c】