【算法】—前缀和与差分详解-Toy模板网

这篇具有很好参考价值的文章主要介绍了【算法】—前缀和与差分详解。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前缀和与差分

1.什么是前缀和

前缀和指一个数组的某下标之前的所有数组元素的和（即数列的前n项求和），前缀和是一种重要的预处理，能够降低算法的时间复杂度，可以快速地求出某一段的和，对于处理区间之间的问题是往往十分高效

相比较其他算法而言，前缀和更像是一种解题的技巧，一种优化方式

0.前缀和的引入：

输入一个长度为 n 的整数序列。接下来再输入 m 个询问，每个询问输入一对 l,r 对于每个询问，输出原序列中从第 l 个数到第 r 个数的和

输入：

输出：

3
6
10

这是一道很简单的题，只用依次将他们循环遍历后加起来即可，但若数据量很大呢？每一次访问都要遍历一次，就会做很多次重复的相加，运算低效，因此，就需要前缀和来降低复杂度

2.一维数组前缀和及差分

1.前缀和

定义：

对一维数组，可以将其前i个元素的和存入sum数组中，这样，每次调用时，只用求sum[i+d]-sum[i]就可以得到区间和了

前缀和,算法,算法,数据结构,python

构造方式：
在构造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.差分

定义：

差分实际上就是构建一个数组，让原数组是差分数组的前缀和数组

前缀和,算法,算法,数据结构,python

构造方式：
同前缀和类似，只是类比地初始化将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
```

前缀和,算法,算法,数据结构,python

示例：

灵能传输

（这是很有思考量的一道题）

思路分析：

首先，对于灵能的传输方式：

①当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相同时，一定存在曲线的最大变化幅度大于直线），所以要使 重叠部分最小：

前缀和,算法,算法,数据结构,python

如图可知，只有当sum数组构成的点集近似的曲线尽可能平稳，其相邻点的差才能尽可能小

确定s0~sn之间的排序及路线：

先对sum[1]~sum[n-1]进行排序（由小到大），因为对于ai的操作就相当于对si和si-1进行交换，这就和冒泡排序一样了，因此任何乱序都能排成有序

前缀和,算法,算法,数据结构,python

首先要清楚（sum[0]==0）和（sum[n]==总能量）是不变的
其次，无论怎么排序，sum[0]和sum[n]一定为起点和终点（因为位置不变，始终位于起始位置）

①sum[0]和sum[n]是最小和最大值：

即sum[0]和sum[n]恰好为起点和终点，则遍历sum[i]-sum[i-1]即可
前缀和,算法,算法,数据结构,python

②sum[0]和sum[n]不是最小和最大值：

如果sum[0]>sum[n]，交换两个值（相当于将曲线反过来看，从sn开始，s0结束）
要满足间隔最小，路线一定为从sum[0]开始走，走到最小值，再从最小值走到最大值，最后由最大值走向sum[n]

前缀和,算法,算法,数据结构,python

确定了大致路线之后，现在要判断能使间隔最短的走法：

排序之后要使跨度尽可能小，可操作的对象就是重叠部分的数该如何走：

如图：
前缀和,算法,算法,数据结构,python

贪心策略：
我们发现 [最小值,s[0]] 和 [s[n],最大值]这两段会走两次，这里我们考虑隔一个取一个数字，因为*如果不是按照这样来取的话，由于每一个数字只可以取一次，第二次取的时候就会使得差值变得更大*

若一个一个走，虽能保证s0~min的每一次的间隔距离（ai）最小，但从min到s0的后一个点跨度过大，无法保证

前缀和,算法,算法,数据结构,python

若选择跨一个走，则可以满足整体跨度均匀

前缀和,算法,算法,数据结构,python

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 阶矩阵内所有元素的和*

（以方格代表数组内每一个元素）：
前缀和,算法,算法,数据结构,python

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] 为对角元素的子矩阵的和为例：
前缀和,算法,算法,数据结构,python

由此推广到一般情况：

若要求以a[x1][y1]和a[x2][y2]为对角顶点元素的子矩阵的和，则可以通过升阶将其转化为x2 × y2阶的矩阵进行处理，其和为：

S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]

前缀和,算法,算法,数据结构,python

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是二维差分数组的前缀和这个条件推导出来的

可以通过下图理解一下：

前缀和,算法,算法,数据结构,python

3.二维差分的主要用处：快速地将一个区块中的所有元素都加上一个值 v

使用差分可以将在数组 arr 上的区块操作转化为在差分数组 d 上的单点操作:

a数组是b数组的前缀和数组，比如对b数组的b[i][j]的修改，会影响到a数组中从a[i][j]及往后的每一个数

如图：

前缀和,算法,算法,数据结构,python

解释：要求只对蓝色区域（小）加上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指针指向第一列，判断此时确定的子矩阵的和是否满足条件：

每次变化都是对列进行操作，因此构造为列的前缀和
1. 若和≤S，移动j2（for循环递增），重复操作，直到找到不满足的列（≥S）为止；
  
  增加列时： *当前和s+=(sum[x2][y2]-sum[x1-1][y2])*
2. 此时≥S，再移动左指针，j1（j1+=1），重复操作，直到找到满足条件的列（≤S）为止，又返回操作1；
  
  减少列时： *当前和s-=(sum[i2][j1]-sum[i1][j1])*
3. 每一轮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 的连续子序列的长度的最小值，即最优连续子序列问题

尺取法的思路与双重循环枚举的思路类似，都是寻找一个区间的起点和终点

图解：

轨迹类似于蚯蚓的爬行，呈阶梯形
前缀和,算法,算法,数据结构,python

②双指针的使用：

双指针本质上也是一种模拟，常用于解决寻找区间和问题

示例：

给定一个序列{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，求最短的子序列长度

双指针的基本思路是:

定义两个指针，将两个指针的看做一个区间范围，且他们最初都指向这一组数中的第一个
如果这个指针区间范围内的元素之和小于给定的数，就把右指针向右移，直到区间和大于等于给定的值为止；

然后把左指针向右移，直到区间和等于给定的值为止；

保存方案，更新最优方案，继续操作——>小于则拓宽有边界，大于则缩小左边界
假如左指针指向这些数的第一个，并且右指针指向这组数的最后一个，这种情况下的子区间元素之和仍然小于给定的数的话，那么就输出 -1，表示不可能