前缀和与差分
文章目录
- 前缀和与差分
- 1.什么是前缀和
- 2.一维数组前缀和及差分
- 1.前缀和
- 2.差分
- 3.二维数组前缀和与差分：
- 1.前缀和
- 2.差分
- 3.双指针
- 4.总结
1.什么是前缀和
前缀和指一个数组的某下标之前的所有数组元素的和（即数列的前n项求和），前缀和是一种重要的预处理，能够降低算法的时间复杂度，可以快速地求出某一段的和，对于处理区间之间的问题是往往十分高效
- 相比较其他算法而言，前缀和更像是一种解题的技巧，一种优化方式
0.前缀和的引入：
输入一个长度为 n 的整数序列。 接下来再输入 m 个询问，每个询问输入一对 l,r 对于每个询问，输出原序列中从第 l 个数到第 r 个数的和
输入：
5 3
2 1 3 6 4
1 2
1 3
2 4
12345
输出：
3
6
10
这是一道很简单的题，只用依次将他们循环遍历后加起来即可，但若数据量很大呢？每一次访问都要遍历一次，就会做很多次重复的相加，运算低效，因此，就需要前缀和来降低复杂度
2.一维数组前缀和及差分
1.前缀和
定义：
对一维数组，可以将其前i个元素的和存入sum数组中，这样，每次调用时，只用求sum[i+d]-sum[i]就可以得到区间和了
构造方式：
在构造sum数组时，有一个小技巧，就是初始化将 sum[0]=0，从下标为1开始记录，为什么要这样构造呢，解释如下：
由于sum[i]表示前i个数的和，所以，sum[0]是没有定义的，又根据sum数组的递推式，当i=1时，可知sum[0]应为0元素：
sum[i ]=sum[i-1 ]+a[i ]
因此，便于求得起点到第i个元素的区间总和即为sum[i]-sum[0]
for i in range(1,n+1):
sum[0]=0
sum[i]=sum[i-1]+a[i]
- 在上述示例代码，我们可以发现初始化前缀和数组中一共执行了n次，因此初始化过程的时间复杂度为O(n)，而在访问过程中，通过直接读取数组中对应的元素来进行求解，时间复杂度为O(1)，因此概括一下即为 O(n)复杂度预处理，O(1)复杂度访问
2.差分
定义：
差分实际上就是构建一个数组，让原数组是差分数组的前缀和数组
构造方式：
同前缀和类似，只是类比地初始化将a[0]=0，其中d[i]表示第i个元素到前一个元素的距离，递推关系为：
d[i]=a[i]-a[i-1]
for i in range(1,n+1):
d[i]=a[i]-a[i-1]
-
差分数组的性质：
1.对差分数组进行前缀和，就可以的到原数组
**原数组： a1 a2 a3 a4 差分数组：a1 a2-a1 a3-a2 a4-a3 前缀和： a1 a2 a3 a4**2.要对数组区间 [ l, r ] 的数据都加上m时，我们只需要对差分数组进行操作即可
- 即 L到前一个元素的距离+c，R到后一个元素的距离-c
d[l]+=c d[r+1]-=c
示例：
灵能传输
（这是很有思考量的一道题）
思路分析：
-
首先，对于灵能的传输方式：
①当ai>0时，传输能量后变为：
a[i]-1 + a[i] -a[i] a[i]+1 + a[i]
②当ai<0时，传输能量后变为：
a[i]-1 + a[i] -a[i] a[i]+1 + a[i]
因此，两种情况的表达式是一样的
并且，构造前缀和数组后（为什么要构造前缀和呢？）：
sum[i] = sum[i-1] + a[i]易得，sum[i-1] = sum[i-1] + a[i] == sum[i]
sum[i] = sum[i] - a[i] == sum[i-1]
结论1：对任意三个连续的数进行灵能传输后，左边两个位置对应的前缀和交换（sum[i]←→sum[i-1]）
-
其次，要求解max（ai）的最小值，即要使max（sum[i] – sum[i-1]）的最小值：
因为能量传输时，仅仅只是能量在各个元素之间的流动，由能量守恒，可知前缀和并不会产生新值，只是在不断进行交换
因此，这也就是为什么要构造前缀和：可以将对元素繁琐的加减的操作转化为对和的多次交换操作
因为sum数组的各项已经确定，若要使相邻差值的最大值最小化，则需要sum数组尽可能单调（因为当▲x相同时，一定存在曲线的最大变化幅度大于直线），所以要使 重叠部分最小：
如图可知，只有当sum数组构成的点集近似的曲线尽可能平稳，其相邻点的差才能尽可能小
- 确定s0~sn之间的排序及路线：
先对sum[1]~sum[n-1]进行排序（由小到大），因为对于ai的操作就相当于对si和si-1进行交换，这就和冒泡排序一样了，因此任何乱序都能排成有序
- 首先要清楚（sum[0]==0）和（sum[n]==总能量）是不变的
- 其次，无论怎么排序，sum[0]和sum[n]一定为起点和终点（因为位置不变，始终位于起始位置）
①sum[0]和sum[n]是最小和最大值：
即sum[0]和sum[n]恰好为起点和终点，则遍历sum[i]-sum[i-1]即可
②sum[0]和sum[n]不是最小和最大值：
- 如果sum[0]>sum[n]，交换两个值（相当于将曲线反过来看，从sn开始，s0结束）
- 要满足间隔最小，路线一定为从sum[0]开始走，走到最小值，再从最小值走到最大值，最后由最大值走向sum[n]
- 确定了大致路线之后，现在要判断能使间隔最短的走法：
排序之后要使跨度尽可能小，可操作的对象就是重叠部分的数该如何走：
如图：
贪心策略：
我们发现 [最小值,s[0]] 和 [s[n],最大值]这两段会走两次，这里我们考虑隔一个取一个数字，因为*如果不是按照这样来取的话，由于每一个数字只可以取一次，第二次取的时候就会使得差值变得更大*
- 若一个一个走，虽能保证s0~min的每一次的间隔距离（ai）最小，但从min到s0的后一个点跨度过大，无法保证
- 若选择跨一个走，则可以满足整体跨度均匀
T=int(input())
for p in range(T):
# 1.初始化
n=int(input())
a=list(map(int,input().split()))
s=[0]+a # s为前缀和数组
for i in range(1,n+1):
s[i]+=s[i-1] # 初始化前缀和数组
sn=s[n]
# 2.对前缀和数组排序（由小到大）
s.sort()
a=[0 for i in range(n+1)]
s0=0
if s0>sn:
sn,s0=s0,sn
for i in range(n+1):
if s[i]==s0:
s0=i # 确定s0位置（起点）
break
for i in range(n,-1,-1):
if s[i]==sn:
sn=i # 确定sn位置（终点）
break
# 3.寻求极差最小的遍历方式
l=0
r=n
a[n]=s[n]
vis=[True for i in range(n+1)]
for i in range(s0,-1,-2): # 从s0到min
a[l]=s[i]
vis[i]=False
l+=1
for i in range(sn,n+1,2): # 从max到sn
a[r]=s[i]
vis[i]=False
r-=1
for i in range(n+1): # 由min到max
if vis[i]:
a[l]=s[i]
l+=1
# 4.找到差值最大值，即为最大能量
res=0
for i in range(n):
res=max(res,abs(a[i+1]-a[i]))
print(res)
3.二维数组前缀和与差分：
1.前缀和
1.定义： 一维数组前缀和（sum[i]）的含义是 一维数组在某一元素之前并包含其本身元素的和
由此推导：
二维数组的前缀和（*s[i][j]*）即为 以 a*[1][1] 和 a[i][j] 为对角顶点元素构成的 ixj 阶矩阵内所有元素的和*
（以方格代表数组内每一个元素）：
2.构造：
因此，二维前缀和递推式为：
s[i][j]=s[i-1][j]+s[i][j-1]+a[i][j]-s[i-1][j-1]
# 二维数组的前缀和(下标从[1][1]开始)
s[i][j] = a[1][1] + a[1][2] + ... + a[1][j]+
a[2][1] + 1[2][2] + ... + 1[2][j]+
a[3][1] + ... + ... + a[3][j]+
+ +
.... ....
+ +
a[i][1] + ... + ... + a[i][j]
那么二维数组前缀和可以用来做什么呢？
以求以 a[3][3] 和 a[5][5] 为对角元素的子矩阵的和为例：
由此推广到一般情况：
若要求以a[x1][y1]和a[x2][y2]为对角顶点元素的子矩阵的和，则可以通过升阶将其转化为x2 × y2阶的矩阵进行处理，其和为：
S[x2, y2] – S[x1 – 1, y2] – S[x2, y1 – 1] + S[x1 – 1, y1 – 1]
2.差分
1.定义：
a数组是b数组的前缀和数组，那么b是a的差分数组
原数组： a[i][j]
差分数组： b[i][j]
使a数组中a[i][j]是b数组左上角(1,1)到右下角(i,j)所包围矩形元素的和
2.二维差分的实现：
对于一个给定的二维数组 arr，它的二维差分数组 d 中 d[i][j] 可以用如下公式计算：
① d[0][0]=a[0][0]
② d[0][j]=a[0][j]-a[0][j-1]
③ d[i][0]=a[i][0]-a[i-1][0]
④ 递推式：b[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1]
上面的公式是通过二维数组 a是二维差分数组的前缀和这个条件推导出来的
可以通过下图理解一下：
3.二维差分的主要用处：快速地将一个区块中的所有元素都加上一个值 v
使用差分可以将在数组 arr 上的区块操作转化为在差分数组 d 上的单点操作:
- a数组是b数组的前缀和数组，比如对b数组的b[i][j]的修改，会影响到a数组中从a[i][j]及往后的每一个数
如图：
解释：要求只对蓝色区域（小）加上c，会使紫色与绿色区域的前缀和数组（a）也加上c，而这两部分原本是不进行操作的，所以要原始数组（b）要集体减去c，又由于红色区域为重合区域实际上被减了两个c，所以还要重新加上一个c
假定我们已经构造好了b数组，类比一维差分，我们执行以下操作 来使被选中的子矩阵中的每个元素的值加上c:
b[x1][y1] + = c b[x1,][y2+1] - = c b[x2+1][y1] - = c b[x2+1][y2+1] + = c
def insert(x1,y1,x2,y2,c)
{
**# 对b数组执行插入操作，等价于对a数组中的(x1,y1)到(x2,y2)之间的元素都加上了c**
b[x1][y1]+=c;
b[x2+1][y1]-=c;
b[x1][y2+1]-=c;
b[x2+1][y2+1]+=c;
}
示例：
统计子矩阵
思路分析：
-
要求满足条件的子矩阵的个数，不难想到二维数组的前缀和
构造列的前缀和数组（之后解释）：sum[i][j]——sum[i][j]=sum[i-1][j]+a[i][j]
-
由于在遍历子矩阵时，四重for循环时间复杂度过高，不能完全通过
因此，引入双指针进行优化：
二维数组实现双指针：
-
因为双指针只是针对一维，因此，考虑逐渐增加行数
-
用两层for循环固定住行区间[i1，i2]，再利用双指针在列上遍历:
注意：每一次遍历前要初始话双指针指向第一列，并将s重新赋为0
-
开始先将j1，j2指针指向第一列，判断此时确定的子矩阵的和是否满足条件：
每次变化都是对列进行操作，因此构造为列的前缀和
-
若和≤S，移动j2（for循环递增），重复操作，直到找到不满足的列（≥S）为止；
增加列时： *当前和s+=(sum[x2][y2]-sum[x1-1][y2])*
-
此时≥S，再移动左指针，j1（j1+=1），重复操作，直到找到满足条件的列（≤S）为止，又返回操作1；
减少列时： *当前和s-=(sum[i2][j1]-sum[i1][j1])*
-
每一轮j2的循环最后都要进行一次满足条件的子矩阵个数的判断：
res+=j2-j1+1
这里相当于将列的右区间固定，接着之前的j1继续增加，看满足条件的j1的个数
-
前缀和（暴力for循环：O（n^4））：
—通过70%样例
N,M,K=map(int,input().split())
a=[[0] for i in range(N)]
a.insert(0,[0]*(M+1))
for i in range(1,N+1): #从a[1]1[1]开始读矩阵
a[i].extend(map(int,input().split()))
ans=0
for i1 in range(1,N+1):
for i2 in range(i1,N+1):
for j1 in range(1,M+1):
for j2 in range(j1,M+1):
sum=0
for i in range(i1,i2+1):
for j in range(j1,j2+1):
sum+=a[i][j]
if sum<=K: #当和不超过 K 时，ans + 1
ans+=1
print(ans)
前缀和+双指针（O（n^3））：
—通过100%样例
def getsum(a):
global sum
for i in range(1,n+1):
for j in range(1,m+1):
sum[i][j]=sum[i-1][j]+a[i][j]
def check(x1,y1,x2,y2):
s=sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1]
if s<=k:
return 1
return 0
# 1.初始化
n,m,k=map(int,input().split())
# 升阶 使sum和a均从[1][1]开始记录
sum=[[0]*(m+1) for i in range(n+1)]
a=[[0]*(m+1)] # 构造的矩阵列表第一行为0
for i in range(1,n+1):
a.append(list(map(int,input().split())))
a[i].insert(0,0)
# 2.构造列的前缀和数组
getsum(a)
print(sum)
# 3.双指针
res=0
for x1 in range(1,n+1):
for x2 in range(x1,n+1):
y1=1;s=0 # 列区间遍历完一次后，要重新初始化，指向1，且和变为0
for y2 in range(1,m+1):
s+=sum[x2][y2]-sum[x1-1][y2] # 每增加一列：增加当前行区间下增加列的值
while s>k:
s-=sum[x2][y1]-sum[x1-1][y1] # 每删去一列，减去当前列的值
y1+=1 # 左区间右移
# if y1>y2: # 若都不满足
# break
res+=y2-y1+1
print(res)
3.双指针
①定义及使用条件：
双指针，也称尺取法，顾名思义，就是像尺子一样一段一段的取，简单来说，尺取法就是定义两个指针i，j确定一个区间，根据条件，交替推进区间的左右两端（即i，j的值交替变化）
一般在以下两种情况使用尺取法：
- 给定一个有序递增数组，在数组中找到满足条件的区间
- 给定长度为 n 的数列以及整数 s，求出不小于 s 的连续子序列的长度的最小值，即最优连续子序列问题
尺取法的思路与双重循环枚举的思路类似，都是寻找一个区间的起点和终点
图解：
轨迹类似于蚯蚓的爬行，呈阶梯形
②双指针的使用：
双指针本质上也是一种模拟，常用于解决寻找区间和问题
示例：
给定一个序列{1，9，-1，-2，7，3，-1，2}，在这些数中找一个区间，使得区间中每个元素的和大于或等于给定的值 S=10，求最短的子序列长度
对于上述问题，不用尺取法的话，肯定就会开双重循环，枚举区间起点和终点，然后每一次都求一次和，再和给定的数作比较。但这样时间复杂度达到 O(n^2)，而使用尺取法，时间复杂度会降到 O(n)
双指针的基本思路是:
-
定义两个指针，将两个指针的看做一个区间范围，且他们最初都指向这一组数中的第一个
-
如果这个指针区间范围内的元素之和小于给定的数，就把右指针向右移，直到区间和大于等于给定的值为止；
然后把左指针向右移，直到区间和等于给定的值为止；
保存方案，更新最优方案，继续操作——>小于则拓宽有边界，大于则缩小左边界
-
假如左指针指向这些数的第一个，并且右指针指向这组数的最后一个，这种情况下的子区间元素之和仍然小于给定的数的话，那么就输出 -1，表示不可能
图解：
示例：
给定一个序列{1，9，-1，-2，7，3，-1，2}，在这些数中找一个区间，使得区间中每个元素的和大于或等于给定的值 S=10，求最短的子序列长度
对于上述问题，不用尺取法的话，肯定就会开双重循环，枚举区间起点和终点，然后每一次都求一次和，再和给定的数作比较。但这样时间复杂度达到 O(n^2)，而使用尺取法，时间复杂度会降到 O(n)
双指针的基本思路是:
-
定义两个指针，将两个指针的看做一个区间范围，且他们最初都指向这一组数中的第一个
-
如果这个指针区间范围内的元素之和小于给定的数，就把右指针向右移，直到区间和大于等于给定的值为止；
然后把左指针向右移，直到区间和等于给定的值为止；
保存方案，更新最优方案，继续操作——>小于则拓宽有边界，大于则缩小左边界
-
假如左指针指向这些数的第一个，并且右指针指向这组数的最后一个，这种情况下的子区间元素之和仍然小于给定的数的话，那么就输出 -1，表示不可能
图解：
4.总结
本篇主要讲解了一种解题技巧——前缀和及差分的原理和用法，也配有一些相应的实例，后续还会更新其他常见的算法，如果有错误请欢迎指正~~，感谢！！！
觉得本篇有帮助的话, 就赏个三连吧~
文章出处登录后可见！
