企业官网建设流程全解析

网站搭建代理,网站备案个人使用,127.0.0. wordpress,优化设计电子版在哪找一.为什么我们要学前缀和 这里我想通过一道例题来解释为什么我们需要学前缀和?学前缀和有什么好处?P8218 【深进1.例1】求区间和 题目描述 给定由 nnn 个正整数组成的序列 a1,a2,⋯ ,ana_1, a_2, \cdots, a_na1​,a2​,⋯,an​ 和 mmm 个区间 [li,ri][l_i,r_i][li​,ri​]分别求这mmm个区间的区间和。输入格式第一行包含一个正整数nnn表示序列的长度。第二行包含nnn个正整数a1,a2,⋯ ,ana_1,a_2, \cdots ,a_na1​,a2​,⋯,an​。第三行包含一个正整数mmm表示区间的数量。接下来mmm行每行包含两个正整数li,ril_i,r_ili​,ri​满足1≤li≤ri≤n1\le l_i\le r_i\le n1≤li​≤ri​≤n。输出格式共mmm行其中第iii行包含一个正整数表示第iii组答案的询问。输入输出样例 #1输入 #14 4 3 2 1 2 1 4 2 3输出 #110 5说明/提示样例解释第111到第444个数加起来和为101010。第222个数到第333个数加起来和为555。数据范围对于50%50 \%50%的数据n,m≤1000n,m\le 1000n,m≤1000对于100%100 \%100%的数据1≤n,m≤1051 \le n, m\le 10^51≤n,m≤1051≤ai≤1041 \le a_i\le 10^41≤ai​≤104。对于这道题,如果我们根据输入临时求区间[l, r]的和,大概率会写出这样的代码for(inti1;im;i){cinlr;sum0;for(intjl;jr;j){suma[j];}}显然,这样的算法的时间复杂度是O(mn)O(mn)O(mn), 肯定会超时,这时我就想引出前缀和,通过此法,可以极大压缩时间复杂度,达到以空间换时间的效果二.前缀和原理1.一维前缀和如图所示,易得prefixSum[i]A[1]A[2]⋯A[i−1]A[i]prefixSum[i] A[1] A[2] \dots A[i - 1] A[i]prefixSum[i]A[1]A[2]⋯A[i−1]A[i]依据此公式我们可以非常轻松的求出[l,r][l, r][l,r]上数组AAA元素的和即,suml,rprefixSum[r]−prefixSum[l−1]sum_{l, r} prefixSum[r] - prefixSum[l - 1]suml,r​prefixSum[r]−prefixSum[l−1]和我们高中所学的数列是一个原理在我们掌握了这个知识点之后, 只需要提前准备好prefixSumprefixSumprefixSum数组,上面那道题就可以这样求解了for(inti1;im;i){cinlr;sumprefixSum[r]-prefixSum[l-1];}此外前缀和还有一个递推公式可以帮助我们求prefixSumprefixSumprefixSum数组prefixSum[i]prefixSum[i−1]A[i]prefixSum[i] prefixSum[i - 1] A[i]prefixSum[i]prefixSum[i−1]A[i]代码示例for(inti1;in;i){cinA[i];prefixSum[i]prefixSum[i-1]A[i];}2.二维前缀和在介绍完了以上比较简单的一维前缀和之后, 我还想再解释一下二维前缀和, 如果遇到给定矩形区域的范围, 我们是否也能用O(1)O(1)O(1)的时间复杂度求出区域内的数值之和呢? 答案当然是肯定的同样的道理prefixSum[i][j]A[1][1]A[1][2]⋯A[1][j−1]A[1][j]A[2][1]A[2][2]⋯A[2][j−1]A[2][j]…A[i][1]A[i][2]⋯A[i][j−1]A[i][j] \begin{aligned} prefixSum[i][j] A[1][1] A[1][2] \dots A[1][j - 1] A[1][j] \\ A[2][1] A[2][2] \dots A[2][j - 1] A[2][j] \\ \dots\\ A[i][1] A[i][2] \dots A[i][j - 1] A[i][j] \end{aligned}prefixSum[i][j]​A[1][1]A[1][2]⋯A[1][j−1]A[1][j]A[2][1]A[2][2]⋯A[2][j−1]A[2][j]…A[i][1]A[i][2]⋯A[i][j−1]A[i][j]​由此我们可以得出以(x1,y1)(x1, y1)(x1,y1)为左上角,(x2,y2)(x2, y2)(x2,y2)为右下角的矩形区域内的元素和公式sum(x1,y1),(x2,y2)prefixSum[x2][y2]−prefixSum[x2][y1−1]−prefixSum[x1−1][y2]prefixSum[x1−1][y1−1] \begin{aligned} sum_{(x1, y1), (x2, y2)} prefixSum[x2][y2] - prefixSum[x2][y1 - 1] -\\ prefixSum[x1 - 1][y2] prefixSum[x1 - 1][y1 - 1] \end{aligned}sum(x1,y1),(x2,y2)​​prefixSum[x2][y2]−prefixSum[x2][y1−1]−prefixSum[x1−1][y2]prefixSum[x1−1][y1−1]​例如, 我们可以轻松算出sum(2,2),(3,4)773110129sum_{(2, 2), (3, 4)} 7 7 3 1 10 1 29sum(2,2),(3,4)​773110129同样也有sum(2,2),(3,4)prefixSum[3][4]−prefixSum[3][1]−prefixSum[1][4]prefixSum[1][1]52−9−16229 \begin{aligned} sum_{(2, 2), (3, 4)} prefixSum[3][4] - prefixSum[3][1] -\\ prefixSum[1][4] prefixSum[1][1] \\ 52 - 9 - 16 2 \\ 29 \end{aligned}sum(2,2),(3,4)​​prefixSum[3][4]−prefixSum[3][1]−prefixSum[1][4]prefixSum[1][1]52−9−16229​其实原理非常简单,利用容斥定理,我们要求出一个矩形区域内的元素和,就用“一个大的,减去两边两个小的,然后多减的一块再加上就行”, 这点结合图示非常容易理解这里还有一个二维前缀和的递推公式可以辅助我们求prefixSumprefixSumprefixSum数组prefixSum[i][j]prefixSum[i][j−1]prefixSum[i−1][j]−prefixSum[i−1][j−1]A[i][j]prefixSum[i][j] prefixSum[i][j - 1] prefixSum[i - 1][j] - prefixSum[i - 1][j - 1] A[i][j]prefixSum[i][j]prefixSum[i][j−1]prefixSum[i−1][j]−prefixSum[i−1][j−1]A[i][j]代码如下for(inti1;in;i){for(intj1;jm;j){cinA[i][j];prefixSum[i][j]prefixSum[i-1][j]prefixSum[i][j-1]-prefixSum[i-1][j-1]A[i][j];}}三.总结不论是一维前缀和还是二维前缀和,都是一种对数据的预处理,然后利用空间换时间的策略,如果这块掌握好了,可以极大的减少时间复杂度,提升代码的通过率后续如果有空,我会在下面贴一些关于本节,且比较适合新手练手的题目…