【差分与前缀和】Python模板

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=" ") 
​

这个代码是一个使用差分数组和前缀和技术来进行区间更新操作的示例。我们逐步解释一下这个程序的逻辑。

  1. 首先,程序读入两个整数N和Q,分别代表数据集合中元素的数量和要进行的操作次数。
  2. nlist 是一个列表,存放着初始的数据集。它通过input().split()获取,分割后转换为整数列表,并在列表的开头插入一个0(这是为了让索引与实际位置对应起来,因为Python的列表索引是从零开始的)。
  3. cf 是差分数组,用于记录每个操作对应范围的增减变化情况,初始化为长度为N+1的全部为0的列表。
  4. 打印nlist,这是为了显示插入0之后的原始数据列表。
  5. 接着,对于每次操作,都会读入三个整数l, r, x,分别代表操作的开始位置、结束位置和要加上的数值。
  6. 差分数组的更新操作如下:在开始位置l加上x,在结束位置的下一个位置r+1减去x。这样的话,当计算区间前缀和时,就可以得知每个位置具体应该增加多少。
  7. 打印更新后的差分数组cf
  8. 接着程序计算差分数组的前缀和,这会转换差分数组为实际从开始位置到当前位置的累积和。
  9. 通过将原始数据列表nlist和差分数组的前缀和相加,得到了所有操作完成后的数据列表anslist
  10. 最后,程序输出最终的更新后的数据列表,如果某个元素小于0,则输出0(可能是为了满足某些约束条件,比如数据不能为负数)。

总之,这个程序的重点在于利用差分数组和前缀和两个技巧:

  • 差分数组 用来高效地处理区间内所有元素的同步更新。
  • 前缀和 根据差分数组计算最终每个位置的数值。

这种方法对于多次区间修改后需要获取最终结果的问题是非常有效率的。

© 版权声明
THE END
点赞10 分享
评论 抢沙发
头像
欢迎您留下宝贵的见解!
提交
头像

昵称

取消
昵称表情代码图片快捷回复

    暂无评论内容