树状数组的第二种用法

作者: yangzhe1991 分类: 我是搞技术的 发布时间: 2012-05-13 19:47 ė 6没有评论

正常的话树状数组是更新某个点的值然后求一个区间的和,这个比较直观也比较常用。树状数组同时也可以更新一个区间求一个点的值,然后这个的原理总是想不起来自己推导也搞不明白查网上的资料也都不是很靠谱(大都是神马修改了函数于是不方便共用一个模板也没意思了)于是趁我现在能搞明白写出来记录下等下次忘了的时候直接看我自己写的东西。

modify理论上是更新某个点的值,sum是求1到这个店的和。

然后假如我想每次更新[l,r]一个区间只求某个点的值就得每次更新若干个点再sum(x)-sum(x-1)。

但是假如我modify(l,k)然后modify(r+1,-k),就会导致sum(l)到sum(r)的值均增加了k,然后[1,l)和(r,max)这两个范围内的sum都不变。

这样sum(x)就是x这个点当前的值了。

本文出自 杨肉的演讲台,转载时请注明出处及相应链接。

本文永久链接: https://yangzhe1991.org/blog/2012/05/%e6%a0%91%e7%8a%b6%e6%95%b0%e7%bb%84%e7%9a%84%e7%ac%ac%e4%ba%8c%e7%a7%8d%e7%94%a8%e6%b3%95/

发表评论

邮箱地址不会被公开。 必填项已用*标注

Ɣ回顶部