文章目录
前言
一、关于前缀和
二、一维数组求前缀和
1.求段区间前缀和
2.例题：AcWing795. 前缀和
AC代码
三、二维数组求前缀和
1.求S[i,j]
2.求（x1，y1），（x2，y2）子矩阵的和
3.例题：AcWing796. 子矩阵的和
AC代码
四、时间复杂度分析
前言
复习acwing算法基础课的内容，本篇为讲解基础算法：前缀和，关于时间复杂度：目前博主不太会计算，先鸽了，日后一定补上.
什么是前缀和：例如一个数组：a[1],a[2],a[3]…a[n]，前缀和S[i]表示的是该数组的前i项的和，例如S[3] = a[1] + a[2] + a[3],S[i] = a[1] + a[2] + a[3] + … + a[i - 1] + a[i].
一、关于前缀和
注：前缀和要求下标从1开始，可以避免下标的转换，对于a[0]的处理：赋值为0即可，从而S[1] = a[0] + a[1] = 0 + a[1] = a[1]；S[2] = a[0] + a[1] + a[2] = 0 + a[1] + a[2] = a[1] + a[2]。对于S[N]，a[N]数组可以定义为全局变量，这样a[0]初始值就为0
前缀和的作用：快速求出某段区间内元素的和
二、一维数组求前缀和
1.求段区间前缀和
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]); //读入n个数 for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + a[i]; //处理前缀和
2.例题：AcWing795. 前缀和
本题链接：AcWing795. 前缀和
本博客给出题目截图：
AC代码
#include <cstdio> using namespace std; const int N = 100010; int a[N], s[N]; int main() { int n, m; scanf("%d%d", &n, &m); 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; }
三、二维数组求前缀和
1.求S[i,j]
如图，用i表示行，j表示列：
根据图分析：求s[i, j]:
s[i, j] = s[i, j - 1] + s[i - 1, j] - s[i - 1, j - 1] + a[i, j];
2.求（x1，y1），（x2，y2）子矩阵的和
如图：
根据图分析：求s[x1 ~ x2, y1 ~ y2]:
s[x1 ~ x2, y1 ~ y2] = s[x2,y2] - s[x2, y1- 1] - s[x1 - 1, y2] + s[x1 - 1,y1 - 1];
3.例题：AcWing796. 子矩阵的和
本题链接：AcWing796. 子矩阵的和
本博客给出题目截图：
AC代码
#include <cstdio> using namespace std; const int N = 1010; int a[N][N], s[N][N]; int main() { int n, m, q; scanf("%d%d%d", &n, &m, &q); for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= m; j ++ ) scanf("%d", &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]; //计算每个s[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; }
四、时间复杂度分析
关于前缀和的时间复杂度以及证明，后续会给出详细的说明以及证明过程，目前先鸽了。
