[Python知识库]D2-AcWing-前缀和&差分795~798

看视频看的有些疲惫，终于可以敲代码了！

一、795前缀和

自己写python模板
无论是nums还是s，下标都是从1开始。

n,m = map(int,input().split())
nums = list(map(int,input().split()))
# 初始化s数组
s = [0]*(n+1) 
for i in range(n):
    s[i+1] += nums[i]+s[i]
while m!=0:
    m -= 1
    l,r = map(int,input().split())
    print(s[r]-s[l-1])

二、796子矩阵的和

这个是一个二维前缀和，求一个区间的和，需要注意的是，在初始化S的时候，下标是从1，1开始的。同时，原数组读入的时候也是从1，1开始的。

n,m,q = map(int,input().split())
A = [[0]*(m+1) for _ in range(n+1)] 
# 读取A
for i in range(n):
    A[i+1][1:] = list(map(int,input().split())) 
# 初始化S
S = [[0]*(m+1) for _ in range(n+1)]
#注意：从1开始哦！
for i in range(1,n+1):
    for j in range(1,m+1):
        S[i][j] = S[i-1][j]+S[i][j-1]-S[i-1][j-1]+A[i][j]
while q!=0:
    q -= 1
    x1,y1,x2,y2 = map(int,input().split())
    print(S[x2][y2]-S[x1-1][y2]-S[x2][y1-1]+S[x1-1][y1-1])

三、797差分

1、注意是在第l到第r个数上加c，一共n个数。
2、B本来有n+1个，第0个空着。由于要表示r+1，所以再多一个。
3、最后输出时，输出A[1]-A[n]。

n,m = map(int,input().split())

A = [0]+list(map(int,input().split()))
# 本来有n+1个数，为了使B[n+1]有意义，所以一共要有n+2个数
B = [0]*(n+2)
# 定义插入函数
def insert(l,r,c):
    B[l] += c
    B[r+1] -= c


# 根据A初始化差分数组B
for i in range(1,n+1):
    insert(i,i,A[i])
# 进行m次操作
while m!=0:
    m -= 1
    l,r,c = map(int,input().split())
    insert(l,r,c)
# A从A[1]开始输出,所以B第一次就是B[0]+B[1]
# 同理，A一共有n个，从A【1】到A【n】
for i in range(1,n+1):
    B[i] += B[i-1]
    print(B[i], end=' ')

798差分矩阵

1、注意矩阵的大小
2、打印二维矩阵时，print（）就换行了。

n,m,q = map(int,input().split())
# 由于差分数组的坐标还是要在后面加个1，也就是x2+1、y2+1，所以还是n+2、m+2个
A = [[0]*(m+2) for _ in range(n+2)]
B = [[0]*(m+2) for _ in range(n+2)]

def insert(x1,y1,x2,y2,c):
    B[x1][y1] += c
    B[x1][y2+1] -=c
    B[x2+1][y1] -=c
    B[x2+1][y2+1] += c
# 读入A    
for i in range(n):
    A[i+1][1:]=list(map(int,input().split()))
# 初始化差分数组B
for i in range(n+1):
    for j in range(m+1):
        insert(i,j,i,j,A[i][j])
# 进行q次操作
while q!=0:
    q -= 1
    x1,y1,x2,y2,c = map(int,input().split())
    insert(x1,y1,x2,y2,c)
for i in range(1,n+1):
    for j in range(1,m+1):
        # B[i][j]还是一点的值，但是等式右边都是前缀和，做完这个假发，B[i][j]也变成前缀和
        B[i][j] += B[i-1][j]+B[i][j-1]-B[i-1][j-1]
        print(B[i][j],end=' ')
    # 直接print()就换行了
    print()