基本算法-03前缀和与差分 学习笔记

一、前缀和

对于一个给定的数列A，它的前缀和数列S时通过递推能求出的基本信息之一。 S [ i ] = ∑ j = 1 i A [ j ] S[i] = \sum_{j = 1}^i A[j] S[i]=j=1∑i​A[j] 一个部分和，即数列A某个下标区间内的和，可以表示为前缀和相减的形式； s u m ( l , r ) = ∑ i = l r A [ i ] = S [ r ] − S [ l − 1 ] sum(l, r) = \sum_{i = l}^r A[i] = S[r] - S[l - 1] sum(l,r)=i=l∑r​A[i]=S[r]−S[l−1] 在二维数组中，可以类似的求出二维前缀和，进一步计算出二维部分和

定义一个二维数组 a[i][j] 则其前缀和为 s [ i ] [ j ] = s [ i ] [ j − 1 ] + s [ i − 1 ] [ j ] − s [ i − 1 ] [ j − 1 ] + a [ i ] [ j ] s [ i ] [ j ] = s [ i ] [ j − 1 ] + s [ i − 1 ] [ j ] − s [ i − 1 ] [ j − 1 ] + a [ i ] [ j ] s[i][j]=s[i][j−1]+s[i−1][j]−s[i−1][j−1]+a[i][j]

那么最大的矩形前缀和就等于蓝的矩阵加上绿的矩阵，再减去重叠面积，最后加上小方块，即 s [ i ] [ j ] = s [ i ] [ j − 1 ] + s [ i − 1 ] [ j ] − s [ i − 1 ] [ j − 1 ] + a [ i ] [ j ] s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + a[i][j] s[i][j]=s[i][j−1]+s[i−1][j]−s[i−1][j−1]+a[i][j]

二、差分

对于一个给定的数列A，它的差分数列B定义为： B [ 1 ] = A [ 1 ] , B [ i ] = A [ i ] − A [ i − 1 ] ( 2 ≤ i ≤ n ) B[1] = A[1], B[i] = A[i] - A[i - 1](2 \le i \le n) B[1]=A[1],B[i]=A[i]−A[i−1](2≤i≤n) 可知：“前缀和”与“差分”为一对逆运算，差分序列B的前缀和序列就是原序列A，前缀和序列S的差分序列也是原序列A。

靶序列A的区间[l, r]加d(即把 Al，AL + 1,…,Ar都加上d)，其差分序列B的变化为Bl加d，Br+1减d，其他位置不便，这有助于我们在许多题目中，把原序列上的“区间操作”转化为差分序列上的“单点操作”进行计算，降低求解复杂度。