前缀和(一维, 二维)
一.为什么我们要学前缀和
这里我想通过一道例题来解释为什么我们需要学前缀和?学前缀和有什么好处?
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
输入 #1
4 4 3 2 1 2 1 4 2 3输出 #1
10 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≤105，1≤ai≤1041 \le a_i\le 10^41≤ai≤104。
对于这道题,如果我们根据输入临时求区间[l, r]的和,大概率会写出这样的代码
for(inti=1;i<=m;i++){cin>>l>>r;sum=0;for(intj=l;j<=r;j++){sum+=a[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,r=prefixSum[r]−prefixSum[l−1]sum_{l, r} = prefixSum[r] - prefixSum[l - 1]suml,r=prefixSum[r]−prefixSum[l−1]
和我们高中所学的数列是一个原理
在我们掌握了这个知识点之后, 只需要提前准备好prefixSumprefixSumprefixSum数组,上面那道题就可以这样求解了
for(inti=1;i<=m;i++){cin>>l>>r;sum=prefixSum[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(inti=1;i<=n;i++){cin>>A[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)=7+7+3+1+10+1=29sum_{(2, 2), (3, 4)} = 7 + 7 + 3 + 1 + 10 + 1 = 29sum(2,2),(3,4)=7+7+3+1+10+1=29
同样也有
sum(2,2),(3,4)=prefixSum[3][4]−prefixSum[3][1]−prefixSum[1][4]+prefixSum[1][1]=52−9−16+2=29 \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−16+229
其实原理非常简单,利用容斥定理,我们要求出一个矩形区域内的元素和,就用
“一个大的,减去两边两个小的,然后多减的一块再加上就行”, 这点结合图示非常容易理解
这里还有一个二维前缀和的递推公式可以辅助我们求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(inti=1;i<=n;i++){for(intj=1;j<=m;j++){cin>>A[i][j];prefixSum[i][j]=prefixSum[i-1][j]+prefixSum[i][j-1]-prefixSum[i-1][j-1]+A[i][j];}}三.总结
不论是一维前缀和还是二维前缀和,都是一种对数据的预处理,然后利用空间换时间的策略,如果这块掌握好了,可以极大的减少时间复杂度,提升代码的通过率
后续如果有空,我会在下面贴一些关于本节,且比较适合新手练手的题目…