【C/C++算法】从浅到深学习--- 前缀和算法（图文兼备 + 源码详解）

绪论：冲击蓝桥杯一起加油！！

每日激励：“不设限和自我肯定的心态：I can do all things。 — Stephen Curry”

绪论​：
本章将使用八道题由浅到深的带你了解并基本掌握前缀和思想，以及前缀和的基本用法！
————————
早关注不迷路，话不多说安全带系好，发车啦（建议电脑观看）。

---

前缀和算法总结：

常规的前缀和分为两种（也是练习1、2）：

1. 一维前缀和：比较简单，在我们需要快速的算出某一数组中的数据时，可以想想是否能使用前缀和，它的使用条件：

   1. 一维数组
   2. 求数组中任意连续的值
   • 对于满足上述条件后就能考虑使用前缀和数组
   • 其中前缀和数组存储dp[ i ]的是：从 1~ i 区域内的元素值之和
   • 其中下标从1开始算，每次创建的数组大小为 n + 1 保证从 1 开始（从1开始是因为： 计算 dp[i] 需要使用 dp[i - 1]，假设 i 不从1开始，若 i 为0，就会越界访问）
   • 具体当我们拥有了一个前缀和数组dp后，使用前缀和数组算出结果，当要求 r ~ l这段区间时它的计算方法就是： dp[ r ] - dp[ l -1 ]
     

2. 二维前缀和：

   1. 条件类似：二维数组，当要求某一块区间的值时 可以考虑使用二维前缀和

   2. 该二维前缀和数组dp[ i ][ j ]中存储的是：从 (0,0) ~ （i,j）区域的所有元素值的和
      

   3. 使用：对于二维前缀和的使用稍微对比起来有点难度，一般来说需要使用到两个公式

      1. 计算出二维前缀和数组中的值的公式：dp[ i ][ j ] = dp[ i ][ j - 1] + dp[ i-1 ][ j ] + arr[ i ][ j ] - dp[ i - 1 ][ j - 1 ]

      对于该公式，切记一定不要死记
      通过下图右边图记忆：
      理解：当我们我们要求的空间可以分为右边图形中的四块：A、B、C、D，其中假如我们从上往下，从左往右的去填写当前的dp数组时，本质上 A、B、C三个区域的值都是已经算好了的，而对于 D 来说他就是自身当前位置的值 arr[ i ][ j ]，所以这样我们就能得出上面的公式：
      A = dp[ i - 1][ j - 1 ]、B = dp[ i - 1][ j ]、C = dp[ i ][ j - 1 ]、D = arr[ i ][ j ]
      

      2. 使用二维前缀和公式快速算出任意两点(x1,y1) ~ (x2,y2)区域的公式：dp[ x2 ][ y2 ] - dp[ x1 - 1 ][ y2 ] - dp[ x2 ][ y1 - 1 ] - dp[ x2 ][ y1 - 1] + dp[ x1 - 1][ y1 - 1 ]

      而对于这个公式来说同样，也是通过一张图进行记忆：
      具体如下就过诉了，这里本质要求的就是 D 区域，如何通过 提前准备好的 二维前缀和数组 求出 D区域的值（同样还是记忆下面右图逻辑即可，必要时画个图）
      

3. 其中前缀和只是个思想，它使用一个数组的形式提前存储一段区间的值，其中这个 区间的值的求法，可能并不一样

   1. 比如存储了 1 ~ i 区间的和、
   2. 存储了 1 ~ i 区间的乘积、
   3. 存储了 1 ~ i 区间的某个数的出现个数…
   4. 再或者是一个后缀和（从后往前的记录其中的值）

• 始终记住前缀和可以用来求出某一段连续区域的值的思想，后面首先会通过两道简单的题（一维和二维前缀和练手），后面将会逐步递增难度（也就代表这个前缀和中存储的并不是 前缀的和）
• 过程中一般都是求某段连续区域中的某个值，对于感觉大脑不够想的时候一定要画图！通过简单的图示更方便的理解和写出公式

具体训练：

1. 一维前缀和【模板】

题目：

分析题目并提出，解决方法：

结合题目分析：

1. 首行是 n ：数组个数、q：查询次数
2. 第二行是有n个元素的数组的值：…
3. 后面有q行，它的值代表查找区间 [左 ~ 右]
4. 那么然后输出查询结果
5. 例如在下面 1 2 4 数组中查找（1,2）、（2,3）、(1,3) 区间的值，具体如下
   
   暴力题解：简单的模拟，根据给q次给的left、right下标，并从该区间【left，right】遍历求和得出答案（O(n * q)的时间复杂度）

对于这种连续数组中求和的情况我们一定要想到前缀和：快速求出数组中某一个连续区间的和
前缀和算法到底是什么？
通过实例来解释：

一维前缀和模板：

1. 预处理出来一个前缀和数组dp（小动态规划）
   1. dp[i]：表示的是 1 ~ i 区间所有元素的和（下标从1开始算，每次创建的数组大小为 n + 1 保证从 1 开始）
      
   2. 并且在计算dp数组的过程中，==dp[ i ] = dp[ i - 1] + arr[ i ]==即可算出（具体分析如上图很好理解），这样更快的求出，不需要每次都遍历真个数组!
   3. 为什么下标从1开始：因为此处要计算 dp[i] 需要使用 dp[i - 1]，i 若为0，就会越界，所以从1开始，这样 即使第一个情况下：1 - 1 = 0 也不会越界
2. 使用前缀和数组
   1. 当我们得到一个前缀和数组后，假设有下情况：
      
   2. 当我们要去 l ~ r 情况的值：就能通过快速的减法得到：dp[ r ] - dp[ l -1 ]
   3. 算法时间复杂度：O(n) + O(q) = O(n)

题解核心逻辑：

1. 根据题目初始化存储好：n,q,数组，查询区域
2. 初始化前缀和数组dp
   1. dp[ i ] = dp[ i - 1] + arr[ i ]
3. 使用前缀和数组算出结果
   1. dp[ r ] - dp[ l -1 ]

代码：

#include <iostream>
#include <vector>
using namespace std;int main() {int n  , q;cin >> n >> q;long long arr[100010] = {0};//根据题目数量级设置，之前设置超过数量级大小的数组即可long long dp[100010] = {0};for(int i = 1; i <= n;i++){//从1开始因为，前缀和需要下标从1开始，留0位置cin >> arr[i];}vector<vector<long long>> lr;//使用vector存储左右区间lr.resize(q);for(int i = 0 ; i < q;i++){int left,right;cin >> left >> right;lr[i].push_back(left);lr[i].push_back(right);}//1. 使用一维前缀和快速求值：//dp[i] = arr[i] + dp[i-1]for(int i = 1; i <= n;i++){dp[i] = arr[i] + dp[i-1];}for(int i = 0 ; i < q;i++){// 使用前缀和求值int l = lr[i][0];int r = lr[i][1];cout << dp[r] - dp[l-1] << endl; }return 0;
}

2. 二维前缀和【模板】

题目：

分析题目并提出，解决方法：

分析题目的例子并理解：

1. 第一行是三个数n,m,q
2. n：代表矩阵数据的行数，m代表矩阵列数，q代表请求查询的参数
3. 其次n行m列的数就是矩阵数据
4. 最后的q行数据代表的是：查询的矩阵的左上角和右下角两点，
5. 过程中可以将数据看成每两个为一个矩阵中的xy点，这样就能得到两点(x1,y1)、(x2,y2)
   如下数据的第一个查询参数值是 1 1 2 2 那么查询的的两点是 (1,1) ~ (2,2)

最终要求的就是这两点矩阵区间的值（如下图）

暴力解法：同样是模拟，根据给的两点的确定查询的矩阵的行列，遍历求和即可

二维前缀和模板：

1. 预处理处一个前缀和矩阵

   1. 创建和原处理矩阵同等大小矩阵dp
   2. 然后对dp中的值进行设置，此处dp内的值和一维前缀和里的值略有不同也更难理解一丢丢，此处二维的是求从 (1,1) ~ （i, i）内这个小矩阵的和，但直接求发现还是表还是得遍历时间复杂度还是比较高，那么在求的过程中就能不能优化下？可以通过利用之前的dp矩阵得出快速求dp[ i ][ j ] = dp[ i ][ j - 1] + dp[ i-1 ][ j ] + arr[ i ][ j ] - dp[ i - 1 ][ j - 1 ]
      具体如下图（注意记住左下角那张分析图，能很好的帮助你理解和记忆公式）：
      

2. 如何使用前缀和矩阵快速取出要求的指定矩阵中的值

   1. 方法类似通过对原矩阵进行分割，通过许多前面算好的矩阵中的值来快速的计算出当前的值，其中划分的步骤很关键，一定要好好理解。
   2. 为什么划分，为了利用之前的值，并且在划分的过程中使用了更简洁的图来更方便理解！
   3. 那么如何使用求出指定的区域能，如下图求D区域，找到左下角点和右下角点，分析该如何划分区间，本质就是要考虑两点的关系
   4. 首先我们可以记住若左上角刚好在整个矩阵的左上角，那么要求的值就是d[x2][y2]的区间的大小
   5. 那么当左上角不在整个原矩阵最左上角时，对于右下角的值来说需要将左上角之外的多余的值给清除（这样记忆更加的好通过图来记忆公式！）

最终划分出来后如下图（注意记住好左边那张分析图，通过这理解这张图帮助你快速理解和记忆公式）

5.最终得出的所要求的区域值就是： dp[ x2 ][ y2 ] - dp[ x1 - 1 ][ y2 ] - dp[ x2 ][ y1 - 1 ] - dp[ x2 ][ y1 - 1] + dp[ x1 - 1][ y1 - 1 ]

题解核心逻辑：

1. 根据题目初始化存储好：n，m，q、矩阵，查询的两点
2. 初始化前缀和矩阵dp
   1. dp[ i ][ j ] = dp[ i ][ j - 1] + dp[ i-1 ][ j ] + arr[ i ][ j ] - dp[ i - 1 ][ j - 1 ]
3. 使用前缀和数组算出结果
   1. dp[ x2 ][ y2 ] - dp[ x1 - 1 ][ y2 ] - dp[ x2 ][ y1 - 1 ] - dp[ x2 ][ y1 - 1] + dp[ x1 - 1][ y1 - 1 ]

代码：

#include <iostream>
using namespace std;
#include <vector>int main() {int n, m, q;cin >> n >> m >> q;long long arr[1010][1010] = {0};long long dp[1010][1010] = {0};for (int i = 1; i <= n;i++) { //从1开始因为，前缀和需要下标从1开始，留0位置for (int j = 1; j <= m; j++) {cin >> arr[i][j];}}vector<vector<long long>> lr;//使用vector存储左右区间lr.resize(q);for (int i = 0 ; i < q; i++) {int x1, y1, x2, y2;cin >> x1 >> y1 >> x2 >> y2;lr[i] = {x1, y1, x2, y2}; //使用initiate}//初始化dp值for (int i = 1; i <= n;i++) { //从1开始因为，前缀和需要下标从1开始，留0位置for (int j = 1; j <= m; j++) {dp[i][j] = arr[i][j] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];// dp[i][j] = A + B + C + D =  D + （A + B） + （A + C）- A}}//使用dp值：for (int i = 0 ; i < q; i++) {int x1 = lr[i][0], y1 = lr[i][1], x2 = lr[i][2], y2 = lr[i][3];cout << dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1] << endl;// D = （x2y2） - B - C - A = （x2y2） - (A+B) - (A+c) + A }return 0;
}
// 64 位输出请用 printf("%lld")

3. 寻找数组的中心下标

题目：

分析题目并提出，解决方法：

分析题目，不难理解示题1的3结果由来：

两种特殊情况：

1. 当没有结果时返回 -1
2. 默认最左边元素的左半区为0，最右边元素的右边区也为0
3. 并且当结果有多个的时候返回最左边的结果

本质所要求的是如下图（ i 的左边区间 = i 的右边区间的 i ）：

本题本质还是在连续数组中找值，那么我们就能使用前缀和思想：

1. 提前预处理好数据到dp中
   1. 现在需要求的就是 （ 0，i - 1 ）、( i + 1，n -1) 这两区间的值
      
   2. 前缀和数组：f [ i ] = f [ i - 1 ] + num [ i - 1 ]
   3. 后缀和数组： g [ j ] = g [ i + 1 ] + num[ i + 1 ]
2. 利用提前处理好的数组，进行题目要求的判断
   1. 假设要判断 i 位置的点是否符合条件 那么就等于判断 f[ i ] == g[ i ]

题解核心逻辑：

1. 创建前缀和数组f：0 ~ i -1、后缀和数组g：i + 1 ~ n - 1
2. 通过前面的公式预处理
   1. f[ i ] = f[ i - 1 ] + arr[ i - 1 ]
   2. g[ i ] = g[ i + 1 ] + arr [ i + 1]
3. 最后遍历数组，找到f[ i ] == g[ i ]处

更多细节见具体代码：

class Solution {
public:static const int CAP = 1e4 + 10;int pivotIndex(vector<int>& nums) {//分析出本题：本质可以通过提前预处理好数组的值来快速计算：前缀和思想//使用前缀和f数组 和 后缀和g数组 存储连续数组的数据int f[CAP] = {0};int g[CAP] = {0};int n = nums.size();//1. 预处理数组//前缀和，f[i] =  0 ~ i - 1for(int i = 1; i <= n;i++){f[i] = f[i-1] + nums[i - 1];//算出 0 ~ i - 1的和}//后缀和，g[i] = i + 1 ~ n - 1for(int i = n - 2;i >= 0;i--){g[i] = g[i+1] + nums[i+1];//g [i] 存储的是 i + 1 ~ n - 1的值//所以当 i = n - 2 存储的就是 n - 1 ~ n - 1的值}//2. 使用预处理数组进行判断for(int i = 0; i < n ;i++)if(f[i] == g[i]) return i;return -1;}
};

4. 除自身以外数组的乘积

题目：

分析题目提出解决方法：

本题本质其实和上一题一样，只不过，本题并不是前缀和，而是前/后 缀积

前缀积、后缀积的算法：

本质也就是将 加法 变成了 乘法（具体如下）

题解核心逻辑：

基本同上就略了

class Solution {
public:static const int CAP = 100010;vector<int> productExceptSelf(vector<int>& nums) {int f[CAP] = {1};//这里是乘法所以等于1int g[CAP];int n = nums.size();g[n - 1] = 1;//处理前缀积for(int i = 1; i <= n;i++){f[i] = f[i-1] * nums[i-1];}
//处理后缀积for(int i = n - 2; i >= 0;i--){g[i] = g[i+1] * nums[i+1];}//使用预处理好的数组：vector<int> ans(n);for(int i = 0; i < n ;i++){ans.push_back(g[i] * f[i]);}return ans;}
};

5. 和为 K 的子数组

题目：

分析题目提出解决方法：

通过例子分析，题目的目的：

暴力解法，就是枚举所有情况（复杂度O(N²)）

分析如何快速找到连续子数组中的值为 k 的子数组

1. 先画一个简单的图来分析：不难发现，若要找以 i 结尾的连续子数组，本质是在 0 ~ i - 1 这个区间找一个值为 sum[ i ] - k 的值有多少个
   （具体如下图，找k长度的区间，可以转换为找sum[ i ] - k 区间的个数，这样就和前面关联了）
   

2. 那如何快速的找出 0 ~ i - 1 区间中 sum[ i ] - k 的个数呢？对于这种数值的查找，可以通过hash表提前存储好

3. 具体hash的使用是：每当查找完一个区间后，将当前下标的 sum[ i ] - k 的值存入hash中

4. 特殊处理：当 sum[ i ] == k 时，查找的区间就是 0 ~ -1 中找 0（sum[i] - k）这本质是不存在的，所以需要提前将hash[0] = 1，因为区间不存在就无法查找，而此时 sum - k = 0，所以就代表自己这个区间就是符合条件的。

5. 其他细节如下：
   

题解核心逻辑：

1. 使用hash表不断记录 0 ~ i - 1 区间中所有sum的情况（因为通过前面的sum情况知道有多少数据为 sum[i] - k）
2. 开始遍历数组，判断是否有值等于当前的 sum - k，若有则代表有符合长度的以i结尾的子数组然后记录个数即可

class Solution {
public:int subarraySum(vector<int>& nums, int k) {//存储 0 ~ i - 1 的sum[i] - k个数（注意这本质存的还是0 ~ i - 1区间中每个元素的sum，只是为了找某个值的 sum = 当前sum - k ）unordered_map<int,int> hash;hash[0] = 1;//特殊处理int count = 0,sum = 0;for(int i = 0;i < nums.size();i++){sum += nums[i];//if(hash.count(sum - k))count += hash[sum - k];hash[sum]++;}return count;}
};

在本题中同样用到了，前缀和的思想，其中加上了hash来代替前缀和，通过hash代替前缀和中记录前面子数组值，从而实现即记录了子数组的值，右记录了相同子数组值的个数

6. 和可被 K 整除的子数组

题目：

分析题目提出解决方法：

本题和上题类似，本题求的是连续子数组和能被k整除个数（上题是找等于k的个数）
直接本题通过例就能看懂了，并且暴力解法也和上类似就不过诉了！

同余定理

同余定理：通过公式理解（具体如下）(a - b) / p = k （余0） -> a % p = b % p

证明过程…：

c++ / java 的负数取模的结果以及修正

1. 负数 % 正数 = 负数 -> 修改为正数：
2. 将值a =（a % p + p）% p（这个公式保证了值无论是 整数还是负数最终都能变成正确取余后的整数）

题解核心逻辑：

同上题一样将数组抽象：
若要再0 ~ i - 1区域中查找一个以i结尾的子数组的和的余数 = 0 的子数组个数
得到下图左边的公式：（sum - x） % k = 0
其中就要使用到同余定理得到：sum % k = x % k（从而得到了 x 区域的求法！：sum % k）
所以本题在上题的基础上修改hash中存储的值：存储的就是所有前缀和的余数的个数

• hash[0] = 1;这里处理的是：当 0 ~ i 区间刚好整除 k，那么 此时 sum % k = 0

class Solution {
public:int subarraysDivByK(vector<int>& nums, int k) {unordered_map<int,int> hash;//一个变化的hash：存储 0 ~ i-1 内所有前缀和的余数的个数hash[0] = 1;//这里处理的是：当 0 ~ i 区间刚好整除 k，那么 此时 sum % k = 0int count1 = 0,sum = 0;for(int i = 0; i < nums.size();i++){sum += nums[i];//前缀和// cout << sum << " " << sum % k << " ";if(hash.count((sum % k + k) % k))count1 += hash[(sum % k + k) % k];//查找 sum % k的个数// cout << hash[sum % k] << " "<< count1 << endl;hash[(sum % k + k) % k]++;//添加 / 创建 sum % k的个数 }return count1;}
};

7. 连续数组

题目：

分析题目提出解决方法：

本题关键：将 0 看出 -1
相信如果从上往下做到了该题，那么你已经具备了一定能力了，下面我就不过多叙述； ，还是那句话遇到难题一定要画图分析
具体分析如下图：

题解核心逻辑：

class Solution {
public:int findMaxLength(vector<int>& nums) {//将 0 看出 -1 //求连续子数组中和为0的个数unordered_map<int,int> hash;//存储前缀和的值和下标// 0 ~ i  sum
// k = 0, 找前缀和等于 sum - 0 = sum 的个数hash[0] = -1;//此处特殊处理：当 0 ~ i 区间为0的情况下 sum就为0，那么查找的区间是不存在的，所以需要提前设置int sum = 0,count =0;int maxlen = 0;for(int i = 0; i < nums.size();i++){sum += (nums[i] == 1 ? 1 : -1);// hash[sum] if(hash.count(sum)){// cout << sum << " " << hash.count(sum) << " " << hash[sum] <<" ";maxlen = max(maxlen,i - hash[sum]);}if(!hash.count(sum)){//判断是否已经存在，若已经存在则不用再记录了，因为最左区间已经确定hash[sum] = i;// cout << sum << " " <<  hash[sum]<<endl;}}return maxlen;}
};

8. 矩阵区域和

题目：

分析题目提出解决方法：

一道二维前缀和的题，理解公式轻松解决
其中注意理解题意：本质就是求以(i,j)为中心的九宫格
分析图如下：

1. 其中注意 dp 的下标是从 1 开始的，所以mat中下标都要-1
   
2. 二维前缀和模板
   
3. 而 ans中的小标是从0开始的，所以使用dp时要+1

4. 注意越界问题

题解核心逻辑：

class Solution {
public:vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {//很清楚的二维前缀和int m = mat.size();int n = mat[0].size(); vector<vector<int>> ans(m,vector<int>(n,0));//创建dp表，并预处理得到所有 从 （0,0） ~ (i,j) 区域的和int dp[110][110] = {0};for(int i = 1 ; i <= m;i++){for(int j = 1; j <= n ;j++){dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + mat[i-1][j-1];cout << dp[i][j] << " ";}cout <<endl;}//最终通过dp表快速的求出所需要的值for(int i = 0; i < m;i++){for(int j = 0; j < n ;j++){int x1 = max(0,i - k) + 1;int y1 = max(0,j - k) + 1;int x2 = min(m-1,i + k) + 1;int y2 = min(n-1,j + k) + 1;// 求 (x1,y1) ~ (x2,y2) 区域的值给到ans即可ans[i][j] = dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1];cout << ans[i][j] << " ";}cout << endl;}return ans;}
};