血浇山花红烂漫，山水无情更依人。欢迎来到丘山望岳的小栈，今天分享的主题是前缀和算法，我们闲言少叙，直击主题。

目录

一维前缀和模板

题目

核心公式：

题目解析

代码

二维前缀和模板

题目

画图分析与核心公式

题目解析

代码

小试牛刀

题目解析

代码

题目解析

代码

题目解析

同余定理（完整定义 + 四大定理 + 严谨证明）

一、基础定义

等价数学表达式（核心）

二、同余四大基本定理及证明

定理 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=k1​m, c−d=k2​m

1. 和：(a+c)−(b+d)=(a−b)+(c−d)=(k1​+k2​)m m 整除该式，故 a+c≡b+d(modm)
2. 差：(a−c)−(b−d)=(a−b)−(c−d)=(k1​−k2​)m 同理得 a−c≡b−d(modm)

定理 2：乘法同余（积不变）

ac≡bd(modm)证明： a=b+k1​m, c=d+k2​m

acac−bd​=(b+k1​m)(d+k2​m)=bd+bk2​m+dk1​m+k1​k2​m2=m(bk2​+dk1​+k1​k2​m)​

右侧是 m 的整数倍，故 m∣(ac−bd)，ac≡bd(modm)

定理 3：幂次同余（乘方不变）

若 a≡b(modm)，对任意正整数 n，有 an≡bn(modm)证明（数学归纳法）

1. 基例 n=1：a1≡b1，显然成立；
2. 归纳假设：设 n=k 时 ak≡bk(modm)；
3. 归纳递推：n=k+1 时 ak+1=ak⋅a,bk+1=bk⋅b 由乘法同余定理：ak⋅a≡bk⋅b(modm) 即 ak+1≡bk+1(modm) 归纳成立，对所有正整数 n 成立。

定理 4：倍数约分同余（重要）

1. 若 a≡b(modm)，整数 k，则 ka≡kb(modm)；
2. 若 ka≡kb(modm)，且 gcd(k,m)=1（k,m 互质），则 a≡b(modm)；

证明

1. a−b=tm，两边乘 k：ka−kb=kt⋅m，m∣ka−kb，得证；
2. 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)。

---

三、同余自反、对称、传递性（等价关系）

1. 自反性：a≡a(modm) 证：a−a=0=m⋅0，m∣0；
2. 对称性：若 a≡b(modm)，则 b≡a(modm) 证：a−b=km⟹b−a=−km，−k 为整数；
3. 传递性：若 a≡b, b≡c(modm)，则 a≡c(modm) 证：a−b=k1​m, b−c=k2​m，相加 a−c=(k1​+k2​)m。

---

四、拓展推论（常用）

1. a≡b(modm)⟹amodm=bmodm；
2. amodm=r⟺a≡r(modm), 0≤r<m；
3. 多个同余式可同时加减乘： a1​≡b1​, a2​≡b2​,…,an​≡bn​(modm) ∑ai​≡∑bi​,∏ai​≡∏bi​(modm)

---

五、举例辅助理解

例：7≡2(mod5)，9≡4(mod5)

1. 和：7+9=16, 2+4=6, 16≡6(mod5)；
2. 积：7×9=63, 2×4=8, 63≡8(mod5)；
3. 幂：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]核心公式中的下标。

今天的分享就到此结束了，感谢观众老爷的支持，恭祝大家：心存太白浩然气，日进陶朱万斗金！