算法——前缀和

一.一维前缀和

来看题目（出自牛客）：

题目要求从一个长度为n的一维数组arr中获取其中[l，r]这段数据的和值，总共获取q次。

首先想到的就是暴力求解，直接遍历数组，然后找到对应的数据段直接计算和。

 但是暴力求解的时间复杂度在特殊情况下会非常的大，比如说，如果q次获取都是整个数组的值的和，那么时间复杂度就达到了O(n * q)，如果 n 和 q 都达到最大范围10 ^ 5，那时间复杂度就是O(10 ^ 10)，这必然导致超时。

因此需要另行他法，设计一个前缀和数组dp，其中dp数组的第 i 位，存放arr数组的前 i 位的和。 

这样设计的好处是什么？

假如说现在要获取arr数组中[3,5]这段数据的和，那就直接让dp[5] - dp[2]即可，dp[5]是arr前5位的和，而dp[2]则是前2位的和，两者相减，就得到想要的结果。

此种方式的时间复杂度仅为O(n + q)。

本题要注意的细节有：

数组arr是从1号下标开始存放数据的，所以创建时其长度应多 + 1；dp数组的长度应和arr的长度一致，且dp数组的0号下标位应置为0，这是为了处理当l为1时，dp[0]的取值有迹可循。由于数据最大可达10^9，所以dp数组应设为long long类型。

C++代码如下（可优化）：

#include <iostream> #include <vector> using namespace std; int main() { int n, q; cin >> n >> q; vector<int> arr; arr.push_back(0); int i = n; while(i--) { int x; cin >> x; arr.push_back(x); } vector<long long> dp; dp.push_back(0); i = 0; long long sum = 0; while(i < n) { sum += arr[i + 1]; dp.push_back(sum); i++; } while(q--) { int l,r; cin >> l >> r; cout << dp[r] - dp[l - 1] << endl; } return 0; }

---

二.二维前缀和

来看题目（出自牛客）： 

在理解一维前缀和的基础上，二维前缀和就是在矩阵中，得到对应范围的值的和。

同样的，如果使用暴力算法，复杂度必然爆炸，不可取，那么继续来看设计前缀和数组的方法。

在矩阵前提下，前缀和数组的每一位 dp[i][j] 则表示，从 arr[1][1] 位置到 arr[i][j] 位置两个顶点构成的矩阵中所有数的和。

那么在矩阵中，该如何去计算dp矩阵的各个位置的大小呢？？？

假如说现在要计算该子矩阵的数据和， 可以将该矩阵分为上述四个区域，其中A区和D区的值分别为 dp[i - 1][j - 1] 和 arr[i][i] ，但是B区和C区的值却不好算，但是B区、C区可以分别与A区合并，这样合并区域的值就分别为 dp[i - 1][j] 和 dp[i][j - 1] ，如此一来整个矩阵的数据和就可以计算为 AB区 + AC区 + D区 - A区。

 如此一来就可以计算得出dp矩阵各个位置的值，构建出dp矩阵。

那么最终结果矩阵的值的和，又该如何计算呢？？？

同样划分为四个区域，要计算D区的大小，我们同样可以采用上边的思想，很容易得出D区 = A + B + C + D - AB - AC + A。

本题要注意的细节：

在进行上述指定矩阵的值的和时，要注意计算dp[AB]、dp[AC]和dp[A]时不能直接使用x1和y1，因为它们代表的是下边一行或一列的下标，应 - 1 才能得到正确的矩阵的dp值。

代码如下：

#include <iostream> #include <vector> using namespace std; int main() { //1.读取数据 int n,m,q; cin >> n >> m >> q; vector<vector<int>> arr(n + 1, vector<int>(m + 1)); for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { cin >> arr[i][j]; } } //2.预处理dp数组 vector<vector<long long>> dp(n + 1, vector<long long>(m + 1)); for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { dp[i][j] = arr[i][j] + dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1]; } } //计算查询结果 int x1,y1,x2,y2; 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; } }

---

三.寻找数组中心下标

来看题目（出自力扣）：

这道题目，需要我们找出数组中一个元素，其前边的所有元素之和等于后边的所有元素之和，如果存在这样的元素，就返回其下标。

根据我们前边分享的前缀和的思想，设计一个前缀和数组（长度为 size + 1），原数组中下标为 i 元素的前边所有元素的和，就是前缀和数组中下标为 i 的元素。而后边所有元素的和，就是用前缀和数组的最后一个元素（原数组的所有元素和），减去下标为 i + 1 的元素。

从左到右遍历，可以满足数组有多个中心下标时，只返回最靠近左边的那一个，如果整个数组都不存在这样的元素，返回-1。

要注意的细节有：

前缀和数组的第0位下标要设为0，用于处理当原数组值全为 0 的场景。

 代码如下：

class Solution { public: int pivotIndex(vector<int>& nums) { int size = nums.size(); vector<int> dp(size + 1); //处理前缀和数组 for(int i = 1;i <= size;i++) { dp[i] = dp[i - 1] + nums[i - 1]; } //遍历前缀和数组寻找 for(int i = 1; i <= size; i++) { int left = dp[i - 1]; int right = dp[size] - dp[i]; if(left == right) return i - 1; } return -1; } };

---

四.总结

前缀和的核心思想在于，当需要对数组中某段连续数据有要求时，可以创建一个前缀和数组来快速处理。