N, Q = map(int,input().split())
nlist = list(map(int, input().split()))
nlist.insert(0, 0)
cf = [0 for _ in range(N+1)]
print(nlist)
for _ in range(Q):
l,r,x = map(int, input().split())
# 在l到r的区间内统一进行操作,只需把l位置的数据操作,在r+1的位置抵消操作即可
cf[l] += x
if r+1<=N:
cf[r+1] -= x
print(cf)
# 计算前缀和
for i in range(1, N + 1):
cf[i] += cf[i - 1]
# 对原始数据+前缀和
anslist = [nlist[i] + cf[i] for i in range(1, N + 1)]
# 输出原始数据
for e in anslist:
if e<0:
print(0, end=" ")
else:
print(e, end=" ")
这个代码是一个使用差分数组和前缀和技术来进行区间更新操作的示例。我们逐步解释一下这个程序的逻辑。
- 首先,程序读入两个整数N和Q,分别代表数据集合中元素的数量和要进行的操作次数。
nlist
是一个列表,存放着初始的数据集。它通过input().split()
获取,分割后转换为整数列表,并在列表的开头插入一个0(这是为了让索引与实际位置对应起来,因为Python的列表索引是从零开始的)。cf
是差分数组,用于记录每个操作对应范围的增减变化情况,初始化为长度为N+1的全部为0的列表。- 打印
nlist
,这是为了显示插入0之后的原始数据列表。 - 接着,对于每次操作,都会读入三个整数l, r, x,分别代表操作的开始位置、结束位置和要加上的数值。
- 差分数组的更新操作如下:在开始位置l加上x,在结束位置的下一个位置r+1减去x。这样的话,当计算区间前缀和时,就可以得知每个位置具体应该增加多少。
- 打印更新后的差分数组
cf
。 - 接着程序计算差分数组的前缀和,这会转换差分数组为实际从开始位置到当前位置的累积和。
- 通过将原始数据列表
nlist
和差分数组的前缀和相加,得到了所有操作完成后的数据列表anslist
。 - 最后,程序输出最终的更新后的数据列表,如果某个元素小于0,则输出0(可能是为了满足某些约束条件,比如数据不能为负数)。
总之,这个程序的重点在于利用差分数组和前缀和两个技巧:
- 差分数组 用来高效地处理区间内所有元素的同步更新。
- 前缀和 根据差分数组计算最终每个位置的数值。
这种方法对于多次区间修改后需要获取最终结果的问题是非常有效率的。
© 版权声明
若无特殊说明,文章版权归作者所有,请勿转载至任何平台。
THE END
暂无评论内容