我爱学算法之—— 前缀和（上）
一、【模板】前缀和
题目解析
这道题，给定一个长度为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>usingnamespace std;constint N =100001;longlong dp[N];int arr[N];int n, m;intmain(){ 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;}return0;}二、【模板】二维前缀和
题目解析
对于这道题，给定一个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>usingnamespace std;constint N =1001;int arr[N][N];longlong dp[N][N];int n, m, q;int x1, x2, y1, y2;intmain(){ 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;}return0;}总结
这里简单总结一下前缀和算法：
首先前缀和算法可以用来快速的求出子数组/子矩阵中所有数的和，在涉及到求子数组/子矩阵的和时，能够利用前缀和算法来快速的求和。
其次，使用前缀和，我们就要预先构建一个前缀和数组并填写该数组；（和动态规划类似）
注意：在构建前缀和数组时，通常下标从1开始，因为在填写数组时要用到dp[i-1]
最后，前缀和算法就是空间换时间，通过预先构建前缀和数组，让我们能够在O(1)的数据复杂度拿到子数组/子矩阵的和。
到这里本篇文章内容就结束了，感谢各位大佬的支持
