我爱学算法之—— 前缀和（上）
一、【模板】前缀和
题目解析
这道题，给定一个长度为
n的数组，和m次询问；每一次询问给出两个整数
l和r，让我们求出区间[l , r]中所有数的和，然后输出。
算法思路
这道题暴力解法：
首先是
m次查询（m次测试），每一个给定一个l和r，让我们求区间[l , r]中所有数的和。暴力解法就非常简单了，直接遍历区间
[l , r]，求出区间中所有数的和即可。
暴力解法时间复杂度O(m * n)，也就是O(n^2)级别的时间复杂度；
暴力解法会超时，我们这里想一想可不可以对暴力解法进行一些优化：
- 首先
m次查询，很显然是不能进行优化的。 - 我们只能对求区间
[l , r]中所有数的和进行优化。
那如何优化呢？
遍历区间
[l , r]来求和时间复杂度是O(n)，那我们可不可以用O(1)的复杂度来获得区间[l , r]中所有数的和呢？
通过上图，我们可以发现：我们要求的[l , r]区间的和s就等于区间[1 , r]的和 减去区间[1 , l]的和。
前缀和
所以，我们可以通过运算来用
O(1)的时间复杂度获得区间[l , r]中所有数的和；但是我们要用到区间[1 , l]和区间[1 , r]中所有数的和。所以我们预先既要处理一个前缀和数组
dp：
- 其中
dp[i]：表示区间[1 , i]中所有数的和。- 填写前缀和数组：
dp[i] = dp[i-1] + arr[i]（也就是前面所有数的和加上当前位置的数）。- 计算区间
[l , r]中所有数的和：dp[r] - dp[l-1]（这里区间[l , r]包含l位置，所以要减去dp[i-1]。
这里可以说：前缀和和动态规划的大致思路非常相似：
状态表示：
dp[i]表示区间[1 , i]中所有数的和状态转移方程：
dp[i] = dp[i] + arr[i];获取区间
[l , r]中所有数的和：s = dp[r] - dp[l-1];
代码实现
#include <cmath>
#include <iostream>
using namespace std;
const int N = 100001;
long long dp[N];
int arr[N];
int n, m;
int main() {cin >> n >> m;for (int i = 1; i <= n; i++) {cin >> arr[i];dp[i] = dp[i - 1] + arr[i];}while (m--) {int l, r;cin >> l >> r;cout << dp[r] - dp[l - 1] << endl;}return 0;
}
二、【模板】二维前缀和
题目解析
对于这道题，给定一个
n*m的二维数组，以及q次查询；每一次查询给定
x1,x2,y1,y2，我们要求以(x1,y1)为左上角，(x2,y2)为右下角的子矩阵中所有数的和。
算法思路
暴力解法：
q次查询，每一查询给定x1,y1,x2,y2，遍历整个子矩阵进行求和操作。
时间复杂度：O(n*m*q)，也就是O(n^3)级别的时间复杂度。
很显然会超时，对暴力解法进行优化，很显然只能优化求子矩阵中所有元素的和。
暴力解法中，遍历整个子矩阵去求和，这样太麻烦了；我们可不可以使用
O(1)的时间复杂度拿到子矩阵中所有数的和？当然也是可以的，这就像数学当中求一块面积的和一样。
如上图所示，我们要求以(x1 , y1)为左上角，(x2 , y2)为右下角的子矩阵中所有数的和，也就是S；
我们只要知道s1（以(1 , 1)为左上角，(x1-1 , y1)为右下角的子矩阵的和）、s2（以(1 , 1)为左上角，(x2, y1-1)为右下角的子矩阵的和）、s3（以(1 , 1)为左上角，(x1-1 , y1-1)为右下角的子矩阵的和）以及s4（以(1 , 1)为左上角，(x2 , y2)为右下角的子矩阵的和）。
我们就可以通过数学运算来求S：s = s4 - s1 - s2 + s3。
也就是s = dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1]
这样我们在填写前缀和表时：
dp[i][j] = dp[i][j-1] +dp[i-1][j] - dp[i-1][j-1] + arr[i][j]
这里也可以将前缀和理解为动态规划
状态表示：
dp[i][j]表示以(1,1)为左上角，(i,j)为右下角的子矩阵中所有数的和。状态转移方程：
dp[i][j] = dp[i][j-1] +dp[i-1][j] - dp[i-1][j-1] + arr[i][j]计算子矩阵中所有数的和：
s = dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1]
代码实现
#include <iostream>
using namespace std;
const int N = 1001;
int arr[N][N];
long long dp[N][N];
int n, m, q;
int x1, x2, y1, y2;int main() {cin >> n >> m >> q;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {cin >> arr[i][j];dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + arr[i][j];}}while (q--) {cin >> x1 >> y1 >> x2 >> y2;cout << (dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1]) << endl;}return 0;
}
总结
这里简单总结一下前缀和算法：
首先前缀和算法可以用来快速的求出子数组/子矩阵中所有数的和，在涉及到求子数组/子矩阵的和时，能够利用前缀和算法来快速的求和。
其次，使用前缀和，我们就要预先构建一个前缀和数组并填写该数组；（和动态规划类似）
注意：在构建前缀和数组时，通常下标从
1开始，因为在填写数组时要用到dp[i-1]最后，前缀和算法就是空间换时间，通过预先构建前缀和数组，让我们能够在
O(1)的数据复杂度拿到子数组/子矩阵的和。
到这里本篇文章内容就结束了，感谢各位大佬的支持