Acwing 797.差分

什么是差分

• 差分思想和前缀和是相反的
• 先定义数组a，其中a[1],a[2]…a[n]作为前缀和
• 然后构造数组b，b[1],b[2]..b[n]为差分数组。通过差分数组的前缀和来表示a数组，即a[n] = b[1] + b[2]…+b[n]

差分的作用

• 例如想要给一个区间[l, r]上的数组加上一个常数c，原始的方法是依次在每个位置加上c，时间复杂度是O(N)的。但是如果采用差分数组，只需要b[l] += c,这样l之后的数字会依次加上常数c，而在b[r]处，需要b[r + 1] -= c。对b数组求一次前缀和，得到a数组，这样就使得在a数组的l，r区间上的每个数加上了c，时间复杂度是O(1)的

如何构造差分数组

• 具体不需要了解构造
• 先假定a数组全为0，在[i, i]的区间插入a[i]则可以得到差分数组b
• 因为插入操作是b[l] += c, b[r + 1] -= c
• b[1] += a[1], b[2] -= a[1]
• b[2] += a[2], b[3] -= a[2]
• 这样最终得到的b[2] = a[2] - a[1], b[1] = a[1],以此类推，自然而然就得到了差分数组b

题解

N = 100010
a = [0] * N
b = [0] * N


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


def main():
    n, m = map(int, input().split(' '))

    a[1: n+1] = list(map(int, input().split(' ')))
    # 构造差分数组b
    for i in range(1, n + 1):
        insert(i, i, a[i]) # 构造方法，可以自己递推一下

    while m:
        m -= 1
        l, r, c = map(int, input().split(' '))

        insert(l, r, c)

    # 对差分数组求一次前缀和，就得到前缀和数组a了
    # 此时的a是经过指定区间加上指定数后的a
    for i in range(1, n + 1):
        a[i] = a[i - 1] + b[i]
        print(a[i], end=' ')


main()