前缀和算法——看这个就够了

血浇山花红烂漫山水无情更依人。欢迎来到丘山望岳的小栈今天分享的主题是前缀和算法我们闲言少叙直击主题。目录一维前缀和模板题目核心公式题目解析代码二维前缀和模板题目画图分析与核心公式题目解析代码小试牛刀题目解析代码题目解析代码题目解析同余定理完整定义 四大定理 严谨证明一、基础定义等价数学表达式核心二、同余四大基本定理及证明定理 1加减同余和差不变定理 2乘法同余积不变定理 3幂次同余乘方不变定理 4倍数约分同余重要三、同余自反、对称、传递性等价关系四、拓展推论常用五、举例辅助理解六、c数学求余数的写法代码二维前缀和压轴题目解析代码易错点归纳一维前缀和模板题目来源牛客网【模板】前缀和_牛客题霸_牛客网https://www.nowcoder.com/practice/acead2f4c28c401889915da98ecdc6bf?tpId230tqId2021480ru/exam/ojqru/ta/dynamic-programming/question-rankingsourceUrl%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] (n1)数列片段元素和公式a[left]a[left1]...a[right]s[right]-s[left-1]其中我们为了防止越界访问和符合数学中的逻辑a[0],s[0]都是0其中a是下标从1开始有有效数据元素的数组s是数组前i项和为s[i]这个元素的数组。题目解析比如数组a【12343566784910】按照题目求解询问t次每次i都不相同。【暴力】每次询问遍历数组求前i项的和求t次时间复杂度Ot*i【一维前缀和优化】先遍历一遍数组通过a[0]0s[0]0s[n]s[n-1]a[n],构造s[n]数组。每次询问通过a[left]a[left1]...a[right]s[right]-s[left-1]迅速求解得出答案。时间复杂度为O(max(n,t))代码#include iostream #includevector using namespace std; int main() { int n,m; cinnm; vectorlong long sum(n1); for(int i1;in1;i) { int a0; cina; sum[i]sum[i-1]a; } while(m--) { int l,r; cinlr; coutsum[r]-sum[l-1]endl; } return 0; }二维前缀和模板题目【模板】二维前缀和_牛客题霸_牛客网给定一个由 行 列整数组成的矩阵 下标均从 开始。 现有 次独立查询第 次。题目来自【牛客题霸】https://www.nowcoder.com/practice/99eb8040d116414ea3296467ce81cbbc?tpId230tqId2023819ru/exam/ojqru/ta/dynamic-programming/question-rankingsourceUrl%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。我们通过上面的图可以看到根据定义只能求得AAB,AC和a[i][j]的值要求s[i][j]的值也就是ABCa[i][j]的值只能通过(AB)(AC)-Aa[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]求解时间复杂度Oi*j)代码#include iostream using namespace std; #includevector int main() { int n,m,t; cinnmt; vectorvectorlong long sum(n1,vectorlong long (m1,0)); for(int i1;in;i) { for(int j1;jm;j) { int temp; cintemp; sum[i][j]sum[i-1][j]sum[i][j-1]temp-sum[i-1][j-1]; } } while(t--) { int a1,a2,b1,b2; cina1b1a2b2; coutsum[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(vectorint nums) { int nnums.size(); vectorlong long fs(n,0); vectorlong long bs(n,0); for(int i1;in;i) { fs[i]fs[i-1]nums[i-1]; } for(int in-2;i0;i--) { bs[i]bs[i1]nums[i1]; } for(int i0;in;i) { if(fs[i]bs[i])return i; } return -1; } };238. 除了自身以外数组的乘积https://leetcode.cn/problems/product-of-array-except-self/题目解析和上面那道题相似只需要建立两个数组一个记录前缀积一个记录后缀积给定下标返回下标映射的两个数组对应元素的乘积。这道题目告诉我们前缀和只是一种思想不一定是和加法运算相关。代码class Solution { public: vectorint productExceptSelf(vectorint nums) { int nnums.size(); vectorint arr(n); vectorint fsum(n1,1);//前缀积数组 vectorint bsum(n1,1);//后缀积数组 //预处理 for(int i1;in;i) fsum[i]fsum[i-1]*nums[i-1]; for(int in-1-1;i0;i--) bsum[i]bsum[i1]*nums[i1]; for(int i0;in;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使得 abkm及a-b可以被k整除。二、同余四大基本定理及证明设 m 为正整数a,b,c,d 为整数且 a≡b(modm),c≡d(modm)定理 1加减同余和差不变ac≡bd(modm),a−c≡b−d(modm)证明 由定义m∣(a−b), m∣(c−d) 即 ∃k1​,k2​∈Za−bk1​m, c−dk2​m和(ac)−(bd)(a−b)(c−d)(k1​k2​)m m 整除该式故 ac≡bd(modm)差(a−c)−(b−d)(a−b)−(c−d)(k1​−k2​)m 同理得 a−c≡b−d(modm)定理 2乘法同余积不变ac≡bd(modm)证明 abk1​m, cdk2​macac−bd​(bk1​m)(dk2​m)bdbk2​mdk1​mk1​k2​m2m(bk2​dk1​k1​k2​m)​右侧是 m 的整数倍故 m∣(ac−bd)ac≡bd(modm)定理 3幂次同余乘方不变若 a≡b(modm)对任意正整数 n有 an≡bn(modm)证明数学归纳法基例 n1a1≡b1显然成立归纳假设设 nk 时 ak≡bk(modm)归纳递推nk1 时 ak1ak⋅a,bk1bk⋅b 由乘法同余定理ak⋅a≡bk⋅b(modm) 即 ak1≡bk1(modm) 归纳成立对所有正整数 n 成立。定理 4倍数约分同余重要若 a≡b(modm)整数 k则 ka≡kb(modm)若 ka≡kb(modm)且 gcd(k,m)1k,m 互质则 a≡b(modm)证明a−btm两边乘 kka−kbkt⋅mm∣ka−kb得证ka−kbm⋅t⟹k(a−b)mt 已知 gcd(k,m)1根据整除性质若 k∣mt,gcd(k,m)1则 k∣t。 设 tk⋅s代入 k(a−b)m⋅ks⟹a−bms 即 m∣a−ba≡b(modm)。三、同余自反、对称、传递性等价关系自反性a≡a(modm) 证a−a0m⋅0m∣0对称性若 a≡b(modm)则 b≡a(modm) 证a−bkm⟹b−a−km−k 为整数传递性若 a≡b, b≡c(modm)则 a≡c(modm) 证a−bk1​m, b−ck2​m相加 a−c(k1​k2​)m。四、拓展推论常用a≡b(modm)⟹amodmbmodmamodmr⟺a≡r(modm), 0≤rm多个同余式可同时加减乘 a1​≡b1​, a2​≡b2​,…,an​≡bn​(modm) ∑ai​≡∑bi​,∏ai​≡∏bi​(modm)五、举例辅助理解例7≡2(mod5)9≡4(mod5)和7916, 246, 16≡6(mod5)积7×963, 2×48, 63≡8(mod5)幂7249, 224, 49≡4(mod5)六、c数学求余数的写法由于c负数求余数的结果和数学求余数不同所以c数学求余数的方式为a%bb)%b有了这个知识补充我们可以将这个问题进行转化求可被k整除的非空子数组就是找一前一后两个同余的前缀和。由于被除数相同我们可以只存放前缀和的余数递推公式可以由上面同余的相关知识推导。但是将这些值放在数组中不能实现快速查找简单估算时间复杂度是On^2)还不如暴力解法。因此我们要动用数据结构来实现这个快速查找的过程。每遍历一个值就将这个值之前元素的前缀和记入哈希表中查找这些数据中和包括当前元素的前缀和的余数相同的值的个数。由于当前元素的前缀和的余数在下一次中的递推公式中会被使用因此单独开一个变量存储这个值。这是蓝桥杯的一道真题题目的具体妙处还要各位读者仔细看代码多多品味。代码class Solution { public: int subarraysDivByK(vectorint nums, int k) { functionint(int,int) mod[](int a,int b)-int{return (a%bb)%b;};//c数学求模公式 int sum0,ret0; unordered_mapint,int hash; hash[0]1; for(auto it:nums) { summod(mod(sum,k)mod(it,k),k);//当前全数组元素之和求模 if(hash.find(sum)!hash.end())rethash[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*k1的正方形二维数组片段和,当然越界问题也要处理,具体细节详见代码。代码class Solution { public: vectorvectorint matrixBlockSum(vectorvectorint mat, int k) { //加边前缀和数组的填充sum[i][j]存放mat[0][0]到mat[i-1][j-1]的元素前缀和 int mmat.size(); int nmat[0].size(); vectorvectorint sum(m1,vectorint(n1)); for(int i1;im1;i) { for(int j1;jn1;j) { sum[i][j]sum[i-1][j]sum[i][j-1]-sum[i-1][j-1]mat[i-1][j-1]; } } //使用前缀和数组解决问题 vectorvectorint ret(m,vectorint (n)); for(int i0;im;i) { for(int j0;jn;j) { int a1max(0,i-k)1,b1max(0,j-k)1,a2min(ik,m-1)1,b2min(jk,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]核心公式中的下标。今天的分享就到此结束了感谢观众老爷的支持恭祝大家心存太白浩然气日进陶朱万斗金