算法——前缀和

一.一维前缀和

来看标题（出自牛客）：

标题要求从一个长度为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++代码如下（可优化）：

1. #include <iostream>
2. #include <vector>
3. using namespace std;
5. int main() {
6.     int n, q;
7.     cin >> n >> q;
8.     vector<int> arr;
9.     arr.push_back(0);
10.     int i = n;
11.     while(i--)
12.     {
13.         int x;
14.         cin >> x;
15.         arr.push_back(x);
16.     }
17.     vector<long long> dp;
18.     dp.push_back(0);
19.     i = 0;
20.     long long sum = 0;
21.     while(i < n)
22.     {
23.         sum += arr[i + 1];
24.         dp.push_back(sum);
25.         i++;
26.     }
27.     while(q--)
28.     {
29.         int l,r;
30.         cin >> l >> r;
31.         cout << dp[r] - dp[l - 1] << endl;
32.     }
33.     return 0;
34. }

复制代码

---

二.二维前缀和

来看标题（出自牛客）： 

在明白一维前缀和的基础上，二维前缀和就是在矩阵中，得到对应范围的值的和。
同样的，假如使用暴力算法，复杂度必然爆炸，不可取，那么继续来看设计前缀和数组的方法。
在矩阵前提下，前缀和数组的每一位 dp[j] 则表示，从 arr[1][1] 位置到 arr[j] 位置两个顶点构成的矩阵中所有数的和。
那么在矩阵中，该怎样去计算dp矩阵的各个位置的巨细呢？？？

假如说现在要计算该子矩阵的数据和， 可以将该矩阵分为上述四个地区，此中A区和D区的值分别为 dp[i - 1][j - 1] 和 arr ，但是B区和C区的值却不好算，但是B区、C区可以分别与A区合并，这样合并地区的值就分别为 dp[i - 1][j] 和 dp[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值。
  

代码如下：

1. #include <iostream>
2. #include <vector>
3. using namespace std;
5. int main()
6. {
7.     //1.读取数据
8.     int n,m,q;
9.     cin >> n >> m >> q;
10.     vector<vector<int>> arr(n + 1, vector<int>(m + 1));
11.     for(int i = 1; i <= n; i++)
12.     {
13.         for(int j = 1; j <= m; j++)
14.         {
15.             cin >> arr[i][j];
16.         }
17.     }
18.     //2.预处理dp数组
19.     vector<vector<long long>> dp(n + 1, vector<long long>(m + 1));
20.     for(int i = 1; i <= n; i++)
21.     {
22.         for(int j = 1; j <= m; j++)
23.         {
24.             dp[i][j] = arr[i][j] + dp[i][j - 1] + dp[i - 1][j] -  dp[i - 1][j - 1];
25.         }
26.     }
27.     //计算查询结果
28.     int x1,y1,x2,y2;
29.     while(q--)
30.     {
31.         cin >> x1 >> y1 >> x2 >> y2;
32.         cout << dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1] << endl;
33.     }
34. }

复制代码

---

三.探求数组中心下标

来看标题（出自力扣）：

这道标题，需要我们找出数组中一个元素，其前边的所有元素之和等于后边的所有元素之和，假如存在这样的元素，就返回其下标。
根据我们前边分享的前缀和的头脑，设计一个前缀和数组（长度为 size + 1），原数组中下标为 i 元素的前边所有元素的和，就是前缀和数组中下标为 i 的元素。而后边所有元素的和，就是用前缀和数组的末了一个元素（原数组的所有元素和），减去下标为 i + 1 的元素。
从左到右遍历，可以满足数组有多个中心下标时，只返回最靠近左边的那一个，假如整个数组都不存在这样的元素，返回-1。
要留意的细节有：

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

 代码如下：

1. class Solution {
2. public:
3.     int pivotIndex(vector<int>& nums) {
4.         int size = nums.size();
5.         vector<int> dp(size + 1);
6.         //处理前缀和数组
7.         for(int i = 1;i <= size;i++)
8.         {
9.             dp[i] = dp[i - 1] + nums[i - 1];
10.         }
11.         //遍历前缀和数组寻找
12.         for(int i = 1; i <= size; i++)
13.         {
14.             int left = dp[i - 1];
15.             int right = dp[size] - dp[i];
16.             if(left == right)
17.                 return i - 1;
18.         }
19.         return -1;
20.     }
21. };

复制代码

---

四.总结

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

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。