题目描述

blablabla

样例

blablabla

算法1

差分

1.a1,a2,a3,…,an
2.构造b1=a1,b2=a2-a1,b3=a3-a2,..,bn=an-a(n-1)
使得an = b1+b2+b3+…+bn
3.a是b的前缀和，b是a的差分
4.作用：对b求前缀和得到a数组。用O(n)的时间得到前缀和数组。
a中一段数都+x,直接做是O(n)的复杂度，用差分的话是O(1)的复杂度
[l,r],b[l]+c可以使a[l]..a[n]所有数都+c。b[l]+c,b[r]-c可以使a[l]…a[r]所有数都+c

python 代码

def insert(l,r,c):
    b[l]+=c
    b[r+1]-=c

if __name__ == "__main__":
    n,q = map(int,input().split())
    a = [0]+ list(map(int,input().split()))
    b = [0]*(n+2)
    for i in range(1,n+1):
        insert(i,i,a[i])
    for i in range(q):
        l,r,c = map(int,input().split())
        insert(l,r,c)
    for i in range(1,n+1):
        b[i]+=b[i-1]
    for i in range(1,n+1):
        print(b[i],end=" ")