柚子快报用激活吗778899分享：【算法】基础算法004之前缀和
樊梓慕：个人主页
个人专栏：《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》《C++》《Linux》《算法》
每一个不曾起舞的日子，都是对生命的辜负
前言
本篇文章为大家带来前缀和算法，前缀和算法可以以O(1)的时间复杂度快速求出某一段连续区间的和，这个连续区域既可以是一维的也可以是二维的。
欢迎大家收藏以便未来做题时可以快速找到思路，巧妙的方法可以事半功倍。
=========================================================================
GITEE相关代码：樊飞 (fanfei_c) - Gitee.com
=========================================================================
1.⼀维前缀和
【模板】前缀和_牛客题霸_牛客网 (nowcoder.com)https://www.nowcoder.com/practice/acead2f4c28c401889915da98ecdc6bf?tpId=230&tqId=2021480&ru=/exam/oj&qru=/ta/dynamic-programming/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196
前缀和：可以快速求出某一段连续区间的和。
本道题目如果使用暴力计算的话会超时，所以需要进行优化。
前缀和解题模板
第一步：预处理出来一个前缀和数组，比如本题dp[i]表示1-i区间内所有元素的和，且dp[i]=dp[i-1]+arr[i]；第二步：使用前缀和数组，比如本题求[l,r]区间元素的和就是dp[r]-dp[l-1]；
#include
#include
using namespace std;
int main() {
// 1.输入数据
int n,q;
cin>>n>>q;
vector
for(int i=1;i<=n;i++) cin>>arr[i];
// 2.预处理出来一个前缀和数组
vector
for(int i=1;i<=n;i++) dp[i]=dp[i-1]+arr[i];
// 3.使用前缀和数组
int l,r;
while(q--)
{
cin>>l>>r;
cout< } return 0; } 注意： 防止溢出，所以dp数据类型选用long long；多开一个空间（n+1）是为了防止越界，因为最后需要[l-1]，所以下标一般都是以1为起始。 2.二维前缀和 【模板】二维前缀和_牛客题霸_牛客网 (nowcoder.com)https://www.nowcoder.com/practice/99eb8040d116414ea3296467ce81cbbc?tpId=230&tqId=2023819&ru=/exam/oj&qru=/ta/dynamic-programming/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196 同样的我们使用前缀和解题模板： 第一步：预处理出来一个前缀和数组，本题中dp[i][j]表示[1,1]-[i][j]区间内所有元素的和。第二步：使用前缀和数组。 首先如何得到状态转移方程，即dp[i][j]如何计算？ 如图所示： 很明显dp[i][j]=A+B+C+D。 但是A还好说，B和C都不好计算。 那么我们就可以把A、B合并为A+B=dp[i-1][j]，把A、C合并为A+C=dp[i][j-1]。 多加了一个A再减去即可。 所以dp[i][j]=(A+B)+(A+C)+D-A=dp[i-1][j]+dp[i][j-1]+arr[i][j]-dp[i-1][j-1]； 其次如何使用前缀和数组？ 同样如上图，[x1][y1]~[x2][y2]的和我们用D块表示。 那么D=A+B+C+D-(A+B)-(A+C)+A=dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1]； #include #include using namespace std; int main() { // 1.输入数据 int n,m,q; cin>>n>>m>>q; vector for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>arr[i][j]; // 2.预处理前缀和矩阵 vector 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]; } } // 3.使用前缀和矩阵 int x1,y1,x2,y2; while(q--) { cin>>x1>>y1>>x2>>y2; cout< } return 0; } 3.练习 724. 寻找数组的中心下标 - 力扣（LeetCode）https://leetcode.cn/problems/find-pivot-index/238. 除自身以外数组的乘积 - 力扣（LeetCode）https://leetcode.cn/problems/product-of-array-except-self/560. 和为 K 的子数组 - 力扣（LeetCode）https://leetcode.cn/problems/subarray-sum-equals-k/ 提示：前缀和+哈希表 974. 和可被 K 整除的子数组 - 力扣（LeetCode）https://leetcode.cn/problems/subarray-sums-divisible-by-k/description/ 补充知识以及思路提示： 1.同余定理 若（a-b）/ p = k ···· 0； //可以整除 则 a % p = b % p； 对于本题来说，我们需要找到可以被k整除的子数组，那么我们假设这段子数组是以i为结尾，x为起始的，整个数组的和为sum，x的前缀和为pre，那么有(sum-pre)%k=0，又因为同余定理可以得到sum%k=pre%k，所以我们只需要将sum%k的结果添加到哈希表中，最后统计哈希表中该余数出现的次数即可，根据后面给出的修正方法，这里求余公式变为（sum%k+k）%k。 2.C++、java对负数 % 正数的结果以及修正 在C++和java语言中负数%正数的结果是一个负数，那么为了让这个负数修正为正数，我们可以利用如下公式： a为负数，b为正数，那么 修正后的余数 = a % b + b，而为了同一处理正负数，我们可以再对这个结果取模，目的是当a为正数时，也不越界。 所以 修正后的余数 = （a%b+b）% b； 525. 连续数组 - 力扣（LeetCode）https://leetcode.cn/problems/contiguous-array/ 思路提示： 本题让我们找出⼀段连续的区间， 0 和 1 出现的次数相同。 • 如果将 0 记为 -1 ， 1 记为 1 ，问题就变成了找出一段区间，这段区间的和等于 0 。 • 于是，就和 『 和为K的子数组』这道题的思路一样了，只不过K的值变为0； 1314. 矩阵区域和 - 力扣（LeetCode）https://leetcode.cn/problems/matrix-block-sum/ 提示：二维前缀和思路 ========================================================================= 如果你对该系列文章有兴趣的话，欢迎持续关注博主动态，博主会持续输出优质内容 博主很需要大家的支持，你的支持是我创作的不竭动力 ~ 点赞收藏＋关注 ~ ========================================================================= 柚子快报用激活吗778899分享：【算法】基础算法004之前缀和 文章来源
发表评论