Algorithm_knowledge

前缀和+差分

前缀和

什么是前缀和，简而言之可以看作数列的前n项之和。

一维前缀和

在一维的线性的前缀和完完全全就可以套用数列求和的$$s_{n}$$，这里我们用到的数列通项公式求和为
$$
s_{n} = s_{n-1}+a_{n} (n>1)\
s_{0} = a_{0}
$$
根据这个公式我们再把模拟过程在python中用列表的形式去模拟，下面给出一个例题模板

有 N 个的正整数放到数组 A 里，现在要求一个新的数组 B，新数组的第 i 个数 B[i] 是原数组 A 第 0 到第 i 个数的和。

输入：
5
1 2 3 4 5
输出：
1 3 6 10 15

n = int(input())
num  = list(map(int,input().split()))
sum_list = [0]*n
for i in range(len(num)):
    if i == 0:
        sum_list[0] = num[0]
    sum_list[i] = sum_list[i-1]+num[i]
for j in sum_list:
    print(j,end=' ')

时间复杂度为$$o(n)$$

在python的itertools库中，有一个accumulate函数刚好实现的就是这个前缀和的功能

import itertools
n = int(input()) #这里的n纯属是因为题目需要保留
num  = list(map(int,input().split()))
sum_list = itertools.accumulate(num)
for j in sum_list:
    print(j,end=' ')

二维或者多维的前缀和

接着我们再来看一下二维的，可以直接用容斥原理来进行计算。

考虑一个具体的例子。

这里 $$s$$是给定矩阵 $$A$$ 的前缀和。根据定义, $$S_{3,3}$$ 是左图中虚线方框中的子矩阵的和。这里, $$S_{3,2}$$是蓝色子矩阵的和， $$S_{2,3}$$是红色子矩阵的和，它们重叠部分的和是 $$S_{2,2}$$。由此可见，如果直接相加 $$S_{3,2}$$和 $$S_{2,3}$$，会重复计算 $$S_{2,2}$$，所以应该有
$$
S_{3,3}=A_{3,3}+S_{2,3}+S_{3,2}-S_{2,2}
$$

#下面是模拟写的一个二维前缀和的代码 自己写的可能有些丑陋
n,m = map(int,input().split())
rectangle = list()
for i in range(n):
    sample = list(map(int,input().split()))
    rectangle.append(sample)
sum_list = [[0]*m for _ in range(n)]
for i in range(n):
    for j in range(m):
        if i == 0 and j == 0:
            sum_list[0][0] = rectangle[0][0]
        elif i == 0 and j != 0:
            sum_list[0][j] = sum_list[0][j-1] + rectangle[0][j]
        elif i != 0 and j == 0:
            sum_list[i][0] = sum_list[i-1][0]+ rectangle[i][0]
        else:
            sum_list[i][j] = rectangle[i][j] + sum_list[i-1][j]+sum_list[i][j-1]-sum_list[i-1][j-1]

一些模拟练习题

1.前缀和 前缀和原题链接

题目简要描述

就是输入一个长度为n的整数序列，再输入m对询问l,r，对于每个询问求出l,r之间的数的和
输出格式
共 m行，每行输出一个询问的结果。
数据范围
1≤l≤r≤n,
1≤n,m≤100000,
−1000≤数列中元素的值≤1000
输入样例：
5 3
2 1 3 6 4
1 2
1 3
2 4
输出样例：
3
6
10

很显然这个题目和上面例题的思路一样，先求出这一序列的前缀和再根据l,r对应的下标进行相减

import sys
n,m = map(int,input().split())
l1 = [0]+list(map(int,sys.stdin.readline().strip().split()))
sum_list = [0]*(n+1)
for i in range(1,len(l1)):
    sum_list[i] = l1[i] + sum_list[i-1]
for _ in range(m):
    l,r = map(int,input().split())
    sum = sum_list[r] - sum_list[l-1]
    print(sum)
print(sum_list)

2.二维前缀和796. 子矩阵的和

题目描述

输入一个n行m列的矩阵输入q个询问，每个询问里包含有x1,y1,x2,y2四个整数分别表示左上坐标和右下坐标
数据范围
1≤n,m≤1000,
1≤q≤200000,
1≤x1≤x2≤n,
1≤y1≤y2≤m,
−1000≤矩阵内元素的值≤1000
输入
3 4 3
1 7 2 4
3 6 2 8
2 1 2 3
1 1 2 2
2 1 3 4
1 3 3 4
输出样例：
17
27
21

这个题目首先从给的范围来看数不算大，最后的最简的时间复杂度应该是$$o(mn)$$到$$o(q)$$之间

因为让求子矩阵的和，这里就可以利用上面的二维前缀和的思路先把矩阵的和，进行一个容斥原理的求解。但是根据x1,y1,x2,y2的范围来看，我们上面的给的模板代码可以再美化一下也就是初始化的时候外面都填一圈0即可。然后就是关于最后的子矩阵的所有数之和：这里我们可以通过划分为四块正方形然后通过容斥原理的逆推就可以得到正确的结果。

(x1-1,y1-1)		(x2,y1-1)
	(x1,y1)
(x1-1,y2)		(x2,y2)

根据如图所示(实在画不出图来了),为了便于表示前缀和这里直接用坐标进行表示:

sum = (x2,y2)-(x2,y1-1)-(x1-1,y2)+(x1-1,y1-1)

下面附上代码

import sys
n,m,q = map(int,sys.stdin.readline().strip().split())
matrix = [[0]*(m+1)]+list([0]+list(map(int,sys.stdin.readline().strip().split())) for _ in range(n))
sum_list = list([0]*(m+1) for _ in range(n+1))
for i in range(1,n+1):
    for j in range(1,m+1):
        sum_list[i][j] = matrix[i][j] + sum_list[i][j-1] + sum_list[i-1][j] - sum_list[i-1][j-1]
for k in range(q):
    x1,y1,x2,y2 = map(int,sys.stdin.readline().strip().split())
    ans = sum_list[x2][y2] - sum_list[x1-1][y2] - sum_list[x2][y1-1] + sum_list[x1-1][y1-1]
    print(ans)

差分

简而言之可以理解为求知道和求通项，也可以理解为前缀和的逆
$$
b_{i} =\begin{cases}
a_{i}-a_{i-1} (i\in \left [ 2,n \right ] )
\
a_{1} \space\space\space i=1
\end{cases}
$$
这里$$a_{i}$$是$$b_{i}$$的前缀和。然后计算$$a_{i}$$的前缀和还可以用$$ \sum_{i=1}^{n} (n-i+1) b_{i}$$

下面先来看到例题

U69096 前缀和的逆

题目简述

简单来说就是给一两个输入n,m。其中n代表输入的个数，m代表输入的前缀和，要还原出每一项的数
输入
6
2 10 20 25 30 43
输出
2 8 10 5 5 13

这道题就是套公式比较简单直接放源码

import sys
n = int(input())
prefix = list(map(int,sys.stdin.readline().strip().split()))
origin = [prefix[0]]+[0]*(n-1)
for i in range(1,n):
    origin[i] = prefix[i] - prefix[i-1]
for j in origin:
    print(j,end=' ')

这里python的原因然后跑的时候第二个用例内存超了，换成c++可以跑通

797. 差分

一维差分

同减一个常数c，这个操作是首先构造一个差分数组，然后再在新构造的差分数组中$$l$$的位置$$+$$或$$-$$个c，再$$r+1$$的位置$$+$$或$$-$$个c。

题目描述

输入一个长度为 n的整数序列。接下来输入 m个操作，每个操作包含三个整数 l,r,c，表示将序列中 [l,r]之间的每个数加上 c。

数据范围
1≤n,m≤100000,
1≤l≤r≤n,
−1000≤c≤1000,
−1000≤整数序列中元素的值≤1000
输入样例：
6 3
1 2 2 1 2 1
1 3 1
3 5 1
1 6 1
输出样例：
3 4 5 3 4 2

很显然是一道模板题只要我们按照上述的思路进行一个模拟即可完成

n,m = map(int,(input().strip().split()))
array = (0,)+tuple(map(int,input().strip().split()))+(0,)  
div = [0]*(n+2)
for i in range(1,n+1):
    div[i] = array[i]-array[i-1]
for _ in range(m):
    l,r,c = map(int,(input().strip().split()))
    div[l] = div[l]+c
    div[r+1] = div[r+1]-c

ans = [0]*(n+2)
for i in range(1,n+1):
    ans[i] = ans[i-1] + div[i]
print(*ans[1:-1]) 

有一点需要注意的是*在python中是解包运算符，对容器类型list,tuple,dict,set解包，接单来说就是把里面的元素给显示出来

**对于字典解包的用法

# 案例一 解包的元素作为参数传给定义的函数
def myfun(name,age):
	print(name,age)
myfun(**dict1)
Mogu134 19

# 案例二 解包两个字典合为一个字典
dict2 = {'nationality':'China','hobby':'eating'}
print({**dict1,**dict2})
{'name': 'Mogu134', 'age': 19, 'nationality': 'China', 'hobby': 'eating'}

**args是用来收集任意数量的实参，并存入到args元组中

**kwargs是用来收集任意数量的关键字实参，存到kwargs字典中

def test(**kwargs):
	print(kwargs)	
test(time='晚上',place='操场',activity='团建')
{'time': '晚上', 'place': '操场', 'activity': '团建'}

差分矩阵

二维差分

二维差分数组的公式可以由二维前缀和的公式倒推，

$$a[i][j] = b[i][j]-b[i-1][j]-b[i][j-1]+b[i-1][j-1]$$

其中$$b[i][j]$$是$$a[i][j]$$的前缀和数组，可以简化记忆右对角线两顶点减左对角线两顶点(自己根据坐标公式总结的便于记忆)。

那么如何让二维差分数组指定区域内的数据同时加或减c

这里可以简单理解为$$a[x1][y1]+=c,a[x2+1][y2+1]+=c$$$$a[x1][y2+1]-=c,a[x2+1][y1]-=c$$

也就是简而言之就是左上角和右下角加c,左下角和右上角减c。具体的推导可以看[这一篇博客](【学习总结】一、二维前缀和 && 一、二维差分-CSDN博客)

内容比较详细

下面来看到题目练练手

题目描述

输入一个 n行m列的整数矩阵，再输入 q个操作，每个操作包含五个整数 x1,y1,x2,y2,c，其中(x1,y1)
和(x2,y2)表示一个子矩阵的左上角坐标和右下角坐标。每个操作都要将选中的子矩阵中的每个元素的值加上 c。
数据范围
1≤n,m≤1000,
1≤q≤100000,
1≤x1≤x2≤n,
1≤y1≤y2≤m,
−1000≤c≤1000,
−1000≤矩阵内元素的值≤1000
输入样例：
3 4 3
1 2 2 1
3 2 2 1
1 1 1 1
1 1 2 2 1
1 3 2 3 2
3 1 3 4 1
输出样例：
2 3 4 1
4 3 4 1
2 2 2 2

这道题就是一个单纯的二维差分矩阵的问题，先构造差分矩阵数组，然后再进行区域内的加减，最后再进行前缀和还原

import sys
n,m,q = map(int,sys.stdin.readline().strip().split())
array = list([[0]*(m+2)])
for _ in range(n):
    array.append([0]+list(map(int,sys.stdin.readline().strip().split()))+[0])
div =[[0]*(m+2) for _ in range(n+2)]  
for i in range(1,n+1):
    for j in range(1,m+1):
        div[i][j] = array[i][j] - array[i-1][j]-array[i][j-1] + array[i-1][j-1]
for _ in range(q):
    x1,y1,x2,y2,c = map(int,sys.stdin.readline().strip().split())
    div[x1][y1] += c
    div[x2+1][y2+1] += c
    div[x1][y2+1] -= c
    div[x2+1][y1] -=c
ans = [[0]*(m+1) for _ in range(n+1)]
for k in range(1,n+1):
    for v in range(1,m+1):
        ans[k][v] = div[k][v]+ans[k-1][v]+ans[k][v-1]-ans[k-1][v-1]
res = ans[1:]
for var in res:
    print(*var[1:])