前缀和算法——看这个就够了
血浇山花红烂漫，山水无情更依人。欢迎来到丘山望岳的小栈，今天分享的主题是前缀和算法，我们闲言少叙，直击主题。
目录
一维前缀和模板
题目
核心公式：
题目解析
代码
二维前缀和模板
题目
画图分析与核心公式
题目解析
代码
小试牛刀
题目解析
代码
题目解析
代码
题目解析
同余定理（完整定义 + 四大定理 + 严谨证明）
一、基础定义
等价数学表达式（核心）
二、同余四大基本定理及证明
定理 1：加减同余（和差不变）
定理 2：乘法同余（积不变）
定理 3：幂次同余（乘方不变）
定理 4：倍数约分同余（重要）
三、同余自反、对称、传递性（等价关系）
四、拓展推论（常用）
五、举例辅助理解
六、c++数学求余数的写法
代码
二维前缀和压轴
题目解析
代码
易错点归纳
一维前缀和模板
题目
来源牛客网：【模板】前缀和_牛客题霸_牛客网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
核心公式：
根据数列求和公式：
s[0]=0,s[n]=a[1]+a[2]+...+a[n]，逐项递推公式s[n]=s[n-1]+a[n] (n>=1)
数列片段元素和公式：a[left]+a[left+1]+...+a[right]=s[right]-s[left-1]
其中我们为了防止越界访问，和符合数学中的逻辑，a[0],s[0]都是0，其中a是下标从1开始有有效数据元素的数组，s是数组前i项和为s[i]这个元素的数组。
题目解析
比如数组a【1，2，3，43，56，6，7，84，9，10】，按照题目求解询问t次，每次i都不相同。
【暴力】每次询问遍历数组，求前i项的和，求t次，时间复杂度O（t*i）
【一维前缀和优化】先遍历一遍数组，通过a[0]=0，s[0]=0，s[n]=s[n-1]+a[n],构造s[n]数组。
每次询问通过a[left]+a[left+1]+...+a[right]=s[right]-s[left-1]迅速求解得出答案。
时间复杂度为O(max(n,t))
代码
#include <iostream> #include<vector> using namespace std; int main() { int n,m; cin>>n>>m; vector<long long> sum(n+1); for(int i=1;i<n+1;i++) { int a=0; cin>>a; sum[i]=sum[i-1]+a; } while(m--) { int l,r; cin>>l>>r; cout<<sum[r]-sum[l-1]<<endl; } return 0; }二维前缀和模板
题目【模板】二维前缀和_牛客题霸_牛客网给定一个由 行 列整数组成的矩阵 （下标均从 开始）。 现有 次独立查询，第 次。题目来自【牛客题霸】![]()
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
题目来源牛客网：
画图分析与核心公式
构造一个二维数组s[a][b],每个元素s[i][j]都是以a[0][0]，a[i][j]这两个元素为对角线矩形子二维数组所有元素之和。与上面同理，为了防止越界情况和符合数学逻辑，a[0][j] a,s数组的第一行，第一列所有元素都赋值为0。
我们通过上面的图可以看到，根据定义，只能求得A，A+B,A+C，和a[i][j]的值，要求s[i][j]的值也就是A+B+C+a[i][j]的值，只能通过(A+B)+(A+C)-A+a[i][j]来求解
所以得到第一个公式：二位前缀和逐项递推公式s[i][j]=a[i][j]+s[i-1[j]+s[i][j-1]-s[i-1][j-1]
同理，如法炮制得到二维前缀和a[i][j]子数矩形组的和公式：s[a1][b1]->s[a2][b2]=sum[a2][b2]-s[a1-1][b2]-s[a2][b1-1]+s[a1-1][b1-1]
题目解析
首先运用递推公式和构造构造一个二维数组s[a][b]，每次询问使用二维前缀和a[i][j]子数矩形组的和公式：s[a1][b1]->s[a2][b2]=sum[a2][b2]-s[a1-1][b2]-s[a2][b1-1]+s[a1-1][b1-1]求解，时间复杂度O（i*j)
代码
#include <iostream> using namespace std; #include<vector> int main() { int n,m,t; cin>>n>>m>>t; vector<vector<long long>> sum(n+1,vector<long long> (m+1,0)); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { int temp; cin>>temp; sum[i][j]=sum[i-1][j]+sum[i][j-1]+temp-sum[i-1][j-1]; } } while(t--) { int a1,a2,b1,b2; cin>>a1>>b1>>a2>>b2; cout<<sum[a2][b2]-sum[a2][b1-1]-sum[a1-1][b2]+sum[a1-1][b1-1]<<endl; } return 0; }小试牛刀
724. 寻找数组的中心下标https://leetcode.cn/problems/find-pivot-index/
题目解析
前缀和的题目原理很简单，关键一招在建模，把问题向两个模板题靠，这里我们要对之前的求和数组s[n]的定义进行调整，原因是题目给出的数组有效元素的下标是从0开始的，我们这里就把s[n]定义为从nums[0]到nums[n-1]这些连续元素的和。不然就会出现s[-1]这样的vector的越界访问。
我们再定义一个后缀和数组fs[n]，记录数组最后一个元素到nums[n-1]这些元素的和，把前缀和数组记为bs[n]，正反依次遍历nums数组，构造前缀和和后缀和数组，当一个元素下标映射到前缀和数组和后缀和数组的值相同时，这就是题目要求的结果。
代码
class Solution { public: int pivotIndex(vector<int>& nums) { int n=nums.size(); vector<long long> fs(n,0); vector<long long> bs(n,0); for(int i=1;i<n;i++) { fs[i]=fs[i-1]+nums[i-1]; } for(int i=n-2;i>=0;i--) { bs[i]=bs[i+1]+nums[i+1]; } for(int i=0;i<n;i++) { if(fs[i]==bs[i])return i; } return -1; } };238. 除了自身以外数组的乘积https://leetcode.cn/problems/product-of-array-except-self/
题目解析
和上面那道题相似，只需要建立两个数组，一个记录前缀积，一个记录后缀积，给定下标返回下标映射的两个数组对应元素的乘积。这道题目告诉我们前缀和只是一种思想，不一定是和加法运算相关。
代码
class Solution { public: vector<int> productExceptSelf(vector<int>& nums) { int n=nums.size(); vector<int> arr(n); vector<int> fsum(n+1,1);//前缀积数组 vector<int> bsum(n+1,1);//后缀积数组 //预处理 for(int i=1;i<n;i++) fsum[i]=fsum[i-1]*nums[i-1]; for(int i=n-1-1;i>=0;i--) bsum[i]=bsum[i+1]*nums[i+1]; for(int i=0;i<n;i++) arr[i]=fsum[i]*bsum[i]; return arr; } };974. 和可被 K 整除的子数组https://leetcode.cn/problems/subarray-sums-divisible-by-k/
题目解析
由于题目给定的原数据数组下标是从0开始的，所以使用的是表示从nums[0]加到nums[n-1]的s[n]才能防止越界。
首先补充一个知识点：
同余定理（完整定义 + 四大定理 + 严谨证明）
一、基础定义
若整数 a,b 除以正整数 m 余数相同，则称a 与 b 模 m 同余，记作： a≡b(modm)
等价数学表达式（核心）
a≡b(modm)⟺m∣(a−b) 即 a−b 能被 m 整除，存在整数 k，使得： a=b+km，及a-b可以被k整除。
二、同余四大基本定理及证明
设 m 为正整数，a,b,c,d 为整数，且 a≡b(modm),c≡d(modm)
定理 1：加减同余（和差不变）
a+c≡b+d(modm),a−c≡b−d(modm)证明： 由定义：m∣(a−b), m∣(c−d) 即 ∃k1,k2∈Z，a−b=k1m, c−d=k2m
- 和：(a+c)−(b+d)=(a−b)+(c−d)=(k1+k2)m m 整除该式，故 a+c≡b+d(modm)
- 差：(a−c)−(b−d)=(a−b)−(c−d)=(k1−k2)m 同理得 a−c≡b−d(modm)
定理 2：乘法同余（积不变）
ac≡bd(modm)证明： a=b+k1m, c=d+k2m
acac−bd=(b+k1m)(d+k2m)=bd+bk2m+dk1m+k1k2m2=m(bk2+dk1+k1k2m)
右侧是 m 的整数倍，故 m∣(ac−bd)，ac≡bd(modm)
定理 3：幂次同余（乘方不变）
若 a≡b(modm)，对任意正整数 n，有 an≡bn(modm)证明（数学归纳法）
- 基例 n=1：a1≡b1，显然成立；
- 归纳假设：设 n=k 时 ak≡bk(modm)；
- 归纳递推：n=k+1 时 ak+1=ak⋅a,bk+1=bk⋅b 由乘法同余定理：ak⋅a≡bk⋅b(modm) 即 ak+1≡bk+1(modm) 归纳成立，对所有正整数 n 成立。
定理 4：倍数约分同余（重要）
- 若 a≡b(modm)，整数 k，则 ka≡kb(modm)；
- 若 ka≡kb(modm)，且 gcd(k,m)=1（k,m 互质），则 a≡b(modm)；
证明
- a−b=tm，两边乘 k：ka−kb=kt⋅m，m∣ka−kb，得证；
- ka−kb=m⋅t⟹k(a−b)=mt 已知 gcd(k,m)=1，根据整除性质：若 k∣mt,gcd(k,m)=1，则 k∣t。 设 t=k⋅s，代入： k(a−b)=m⋅ks⟹a−b=ms 即 m∣a−b，a≡b(modm)。
三、同余自反、对称、传递性（等价关系）
- 自反性：a≡a(modm) 证：a−a=0=m⋅0，m∣0；
- 对称性：若 a≡b(modm)，则 b≡a(modm) 证：a−b=km⟹b−a=−km，−k 为整数；
- 传递性：若 a≡b, b≡c(modm)，则 a≡c(modm) 证：a−b=k1m, b−c=k2m，相加 a−c=(k1+k2)m。
四、拓展推论（常用）
- a≡b(modm)⟹amodm=bmodm；
- amodm=r⟺a≡r(modm), 0≤r<m；
- 多个同余式可同时加减乘： a1≡b1, a2≡b2,…,an≡bn(modm) ∑ai≡∑bi,∏ai≡∏bi(modm)
五、举例辅助理解
例：7≡2(mod5)，9≡4(mod5)
- 和：7+9=16, 2+4=6, 16≡6(mod5)；
- 积：7×9=63, 2×4=8, 63≡8(mod5)；
- 幂：72=49, 22=4, 49≡4(mod5)
六、c++数学求余数的写法
由于c++负数求余数的结果和数学求余数不同，所以c++数学求余数的方式为（a%b+b)%b
有了这个知识补充，我们可以将这个问题进行转化，求可被k整除的非空子数组，就是找一前一后两个同余的前缀和。由于被除数相同，我们可以只存放前缀和的余数，递推公式可以由上面同余的相关知识推导。
但是将这些值放在数组中，不能实现快速查找，简单估算时间复杂度是O（n^2)还不如暴力解法。
因此我们要动用数据结构来实现这个快速查找的过程。
每遍历一个值，就将这个值之前元素的前缀和记入哈希表中，查找这些数据中和包括当前元素的前缀和的余数相同的值的个数。
由于当前元素的前缀和的余数在下一次中的递推公式中会被使用，因此单独开一个变量存储这个值。
这是蓝桥杯的一道真题，题目的具体妙处还要各位读者仔细看代码多多品味。
代码
class Solution { public: int subarraysDivByK(vector<int>& nums, int k) { function<int(int,int)> mod=[](int a,int b)->int{return (a%b+b)%b;};//c++数学求模公式 int sum=0,ret=0; unordered_map<int,int> hash; hash[0]=1; for(auto it:nums) { sum=mod(mod(sum,k)+mod(it,k),k);//当前全数组元素之和求模 if(hash.find(sum)!=hash.end())ret+=hash[sum];//找到同余的前缀和（同余定理） hash[sum]++; } return ret; } };二维前缀和压轴
1314. 矩阵区域和https://leetcode.cn/problems/matrix-block-sum/
题目解析
我们注意到，题目给定的数组是横纵下标从0开始是有效元素的数组，故而我们要在构造前缀和数组中给数组加两条边：有效数据前缀和存储横纵下标从1开始，第0行，第0列赋值为0，否则会出现数组的越界访问问题。
对照模板，模板中的nums[i][j] 其实是本题数据中的mat[i-1][j-1],所以相应的公式也要做出修改。
构造前缀和数组成功后直接使用，依照题意，answer[i][j]就是以mat[i][j]为中心，向上下左右k个元素长度，十字覆盖的长度为2*k+1的正方形二维数组片段和,当然，越界问题也要处理,具体细节详见代码。
代码
class Solution { public: vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) { //加边前缀和数组的填充sum[i][j]存放mat[0][0]到mat[i-1][j-1]的元素前缀和 int m=mat.size(); int n=mat[0].size(); vector<vector<int>> sum(m+1,vector<int>(n+1)); for(int i=1;i<m+1;i++) { for(int j=1;j<n+1;j++) { sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+mat[i-1][j-1]; } } //使用前缀和数组解决问题 vector<vector<int>> ret(m,vector<int> (n)); for(int i=0;i<m;i++) { for(int j=0;j<n;j++) { int a1=max(0,i-k)+1,b1=max(0,j-k)+1,a2=min(i+k,m-1)+1,b2=min(j+k,n-1)+1; ret[i][j]=sum[a2][b2]-sum[a1-1][b2]-sum[a2][b1-1]+sum[a1-1][b1-1]; } } return ret; } };易错点归纳
前缀和的重点是数学建模解决问题，将一个实际的数学问题套模板转化为使用前缀和可以解决的问题。关键是处理数组越界，在模板中我们的原始数据数组nums和前缀和数组都是第0个元素（二维：第0行，第0列元素）不存储任何值的。但是大部分题目都是给定数据数组从第0个元素（二维：第0行，第0列元素）开始存储有效数据的，这里解决思路有两种：一种是像leetcode724题（见上）那样微调前缀和定义：定义sum[0]=0,sum[i]=nums[0]+nums[1]+...+nums[i-1].
或者是leetcode1314题（见上）保留前缀和模板中的原始定义，微调涉及nums[i][j]核心公式中的下标。
今天的分享就到此结束了，感谢观众老爷的支持，恭祝大家：心存太白浩然气，日进陶朱万斗金！