---

前言

复习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;
}

四、时间复杂度分析

关于前缀和的时间复杂度以及证明，后续会给出详细的说明以及证明过程，目前先鸽了。