思路:(取一次查询为例)
1、采用差分的思想
2、创建差分数组diff并将每一位初始化为0
3、把差分数组diff第 l 个元素 + c , 第 r + 1 个元素 -c
4、对差分数组求前缀和,这样差分数组[l , r]上的元素都为c
5、将原数组加上差分数组,这样原数组上[l , r]上的元素都加上了c
时间复杂度
O(m + n)
代码
if __name__ == "__main__":
n, m = map(int, input().split())
seq = list(map(int, input().split()))
# 创建差分数组
diff = [0]*n
# 将第 l 个元素+c, 第r + 1个元素 -c
for _ in range(m):
l, r, c = map(int, input().split())
diff[l-1] += c
if r < n:
diff[r] -= c
# 对差分数组进行前缀和操作
for i in range(1, n):
diff[i] += diff[i-1]
# 根据差分数组计算前缀和得到结果
for i in range(n):
seq[i] += diff[i]
print(*seq)
一些问题的回答
1、为什么对差分数组求前缀和是从下标1开始的
从下标 1 开始的目的是为了保持差分数组与原始序列的对应关系,这是由创建的原始数组决定的
差分数组 diff 的每个元素表示原始序列中相邻两个元素的差值。通过对差分数组进行前缀和操作,可以得到一个新的数组 prefix_sum,其中 prefix_sum[i] 表示原始序列中从下标 0 到下标 i 的元素的和。
如果我们从下标 0 开始进行前缀和操作,即 prefix_sum[0] = diff[0],那么 prefix_sum[i] 表示原始序列中从下标 0 到下标 i-1 的元素的和,而不是从下标 0 到下标 i 的元素的和。这样的话,差分数组与原始序列的对应关系就会出现偏差。
2、为什么不从1开始循环将diff[l] += c ,diff[r + 1] -= c
为了避免方便处理边界情况,确保进行前缀和使差分数组的每一个元素都与操作中的每一个元素对应。但这并不是必须的,可以通过其他方式使diff[l] += c ,diff[r + 1] -= c并达到目的
3、为什么最后输出的*seq
为了保持数组一致性,我们使用*seq表示原始序列,表示按照原始序列的位置输出对应的值
在差分数组的前缀和操作中,我们得到的是一个新的数组 prefix_sum,其中 prefix_sum[i] 表示原始序列中从下标 0 到下标 i 的元素的和。
然而,在实际应用中,我们可能更关心的是原始序列中每个位置的值,而不仅仅是前缀和。为了得到原始序列,我们需要根据差分数组的前缀和计算出原始序列中每个位置的值。
具体做法是,我们从原始序列的第一个位置开始,依次将前缀和与当前位置的值相加,得到原始序列中每个位置的值。这样,我们就可以得到一个新的序列 sequence,其中 sequence[i] 表示原始序列中第 i 个位置的值。
由于差分数组的前缀和操作是从下标 1 开始的,而原始序列的下标是从 0 开始的,因此在计算原始序列时,需要将 prefix_sum[i] 加到 sequence[i-1] 上,得到 sequence[i]。
为了保持一致性,我们在输出结果时使用 *sequence 表示原始序列,而不是 sequence。这样可以提醒读者注意到这是一个指针,指向原始序列的首地址。