题解 | #【模板】差分#

利用差分数组 diff 减少区间操作的时间复杂度, diff 生成如下:

diff[0] = data[0]
for i in range(1, len(data)):
    # 后一个元素与前一个元素相减
    diff[i] = data[i] - data[i - 1]

之后可根据 diff 依次推算出 data 的值;

data[0] = diff[0]
for i in range(1, len(diff)):
    data[i] = data[i - 1] + diff[i]

这样在对 data[i:j + 1] 进行加减值操作时, 可对 diff[i] 和 diff[j + 1] 的值操作即可, data[i:j + 1] + k 则 diff[i] + k, diff[j + 1] - k，如此在求值时,data[i:j + 1] 均增加 k;

n, m = map(int, input().strip().split())
data = list(map(int, input().strip().split()))
diff = [0 for _ in range(n)]
diff[0] = data[0]
for i in range(1, n):
    diff[i] = data[i] - data[i - 1]
for i in range(m):
    l, r, k = map(int, input().strip().split())
    if l > n:
        continue
    diff[l - 1] += k
    if r >= n:
        continue
    diff[r] -= k
res = [0 for _ in range(n)]
res[0] = diff[0]
for i in range(1, n):
    res[i] = diff[i] + res[i - 1]
print(" ".join(map(str, res)))