> 作者：დ旧言~
> 座右铭：松树千年终是朽，槿花一日自为荣。
> 目标：熟练掌握前缀和算法。
> 毒鸡汤：学习，学习，再学习 ! 学，然后知不足。
> 专栏选自：刷题训练营
> 望小伙伴们点赞👍收藏✨加关注哟💕💕
🌟前言分析
最早博主续写了牛客网130道题，这块的刷题是让同学们快速进入C语言，而我们学习c++已经有一段时间了，知识储备已经足够了但缺少了实战，面对这块短板博主续写刷题训练，针对性学习，把相似的题目归类，系统的刷题，而我们刷题的官网可以参考：
⭐知识讲解
前缀和只是一个算法的总称，其实前缀和可以分为前缀和，前缀积，这类算法更像是高中我们所学的数列的求和，寻找一组数列的规律，从而计算前缀和，这类题目很有规律的，学会画图，掌握题目的所隐藏的规律，这类题目就自然而然的可以解出。
⭐经典题型
🌙topic-->1
题目链接：1.前缀和
题目分析：
输入 n 个数字 ,求 q 次前缀和，这个 q 次前缀和范围在 l ~ r 之间 （不是数组的下标，而是数组第l 的数），输出多组数据。
算法原理：
- 解法一：
暴力遍历数组，时间复杂度为O(n * q)，这个解法会超时，所以我们不用这个算法。
- 解法二：
采用前缀和的算法原理：
代码演示：
#include <iostream> using namespace std; const int N = 100001; // 数据大小 long long arr[N],dp[N]; int n,q; int main() { // 输入 cin >> n >> q; // 存入数据 for(int i = 1;i <= n;i++) cin >> arr[i]; // 前缀和 for(int i = 1;i <= n;i++) dp[i] = dp[i - 1] + arr[i]; // 输出 while(q--) { int l,r = 0; cin >> l >> r; // 计算前缀和 cout << dp[r] - dp[l - 1] << endl; } return 0; }
🌙topic-->2
题目链接：2二维前缀和
题目分析：
在一个二维数组（ n * m）中，求 q 次二维前缀和，其中需要输入两个二维坐标，求输入这个两个坐标矩阵的和。
算法原理：
- 解法一：
暴力遍历二维数组，时间复杂度为O(n * m * q)，这个解法会超时，所以我们不用这个算法。
- 解法二：
采用二维前缀和的算法原理：
代码演示：
#include <iostream> using namespace std; const int N = 1001; // 数据大小 int arr[N][N]; long long dp[N][N]; int n,m,q = 0; int main() { // 输入 cin >> n >> m >> q; // 读入数据 for(int i = 1 ;i <= n;i++) for(int j = 1;j <= m;j++) cin >> arr[i][j]; // 处理数据 for(int i = 1;i <=n;i++) for(int j = 1;j <= m;j++) dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + arr[i][j] - dp[i - 1][j - 1]; // 使用前缀和矩阵 int x1,y1,x2,y2 = 0; 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; }
🌙topic-->3
题目链接：3.前缀和
题目分析：
数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。
如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。
算法原理：
- 解法一：
暴力遍历一维数组，这个解法会超时，所以我们不用这个算法。
- 解法二：
采用一维前缀和的算法原理：
代码演示：
class Solution { public: int pivotIndex(vector<int>& nums) { // lsum[i] 表⽰：[0, i - 1] 区间所有元素的和 // rsum[i] 表⽰：[i + 1, n - 1] 区间所有元素的和 int n = nums.size(); vector<int> lsum(n), rsum(n); // 预处理前缀和后缀和数组 for (int i = 1; i < n; i++) lsum[i] = lsum[i - 1] + nums[i - 1]; for (int i = n - 2; i >= 0; i--) rsum[i] = rsum[i + 1] + nums[i + 1]; // 判断 for (int i = 0; i < n; i++) if (lsum[i] == rsum[i]) return i; return -1; } };
🌙topic-->4
题目链接：4.前缀和
题目分析：
给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
算法原理：
- 解法一：
暴力遍历一维数组，这个解法会超时，所以我们不用这个算法。
- 解法二：
采用一维前缀积的算法原理：
代码演示：
class Solution { public: vector<int> productExceptSelf(vector<int>& nums) { // lprod 表⽰：[0, i - 1] 区间内所有元素的乘积 // rprod 表⽰：[i + 1, n - 1] 区间内所有元素的乘积 int n = nums.size(); vector<int> lprod(n + 1), rprod(n + 1); lprod[0] = 1, rprod[n - 1] = 1; // 预处理前缀积以及后缀积 for (int i = 1; i < n; i++) lprod[i] = lprod[i - 1] * nums[i - 1]; for (int i = n - 2; i >= 0; i--) rprod[i] = rprod[i + 1] * nums[i + 1]; // 处理结果数组 vector<int> ret(n); for (int i = 0; i < n; i++) ret[i] = lprod[i] * rprod[i]; return ret; } };
刷题训练之前缀和（下） https://developer.aliyun.com/article/1565746
