题解 P2068 【统计和】

Suuon_Kanderu

2020-03-12 17:45:04

Solution

树状数组是一种用来维护区间操作的数据结构 如图,一个维护和的一个树状数组。 因为直接看十进制看不出什么套路,好心的我转换成了二进制。 你可以清晰的发现很多性质,下面我来捋一捋: ![](https://cdn.luogu.com.cn/upload/image_hosting/9t3bv5s8.png) - 设树状数组为$C_i$,正常数组为$A_i$。 - 首先我们定义一个函数 $\operatorname {lowbit} k $ 表示二进制中最右边“1”的位置(你可能觉得奇怪但这个函数很有用。 - 单点修改: 随便举个例子,比如将$A_{0001} + 5$,看图我们要将$C_{0001} + 5,C_{0010} + 5,C_{0100} + 5,C_{1000} + 5$,很容易看出规律: 每个增加的下标都是原有的下标 i 加上 $ \operatorname {lowbit}i $ 有人可能要问了不就是1的位置往右移动了1位吗?你扯出个 lowbit 有啥用? 不急,换个例子,比如把$A_{0011} + 5$,就要把 $C_{0100}+5,C_{1000} + 5$。 在这个例子中, $\operatorname {lowbit}0011 = 1 $ , $0011 + \operatorname {lowbit}0011 = 0100$。 $\operatorname {lowbit}0100 = 3 $ , $ 0100 + \operatorname {lowbit}0100 = 1000$ 。 看吧,全部吻合了。 ![](https://cdn.luogu.com.cn/upload/image_hosting/9t3bv5s8.png) (为了不让你们翻页看,我给你们再加一次 ) - 区间查询 : 树状数组来求 1 到 N 的区间和比较方便,但我们如何求 K 到 N 的区间和呢? 只需要让 1 到 N 的和 减去 1到 K-1 的和。(前缀和思想) 也来个例子,求$\sum\limits_{i = 1}^{n=7}A_i$,你们可能知道了,肯定又和 $\operatorname {lowbit} $ 有关,它 等于 $C_{0111} + C_{0111- \operatorname{lowbit}0111}(0110) + C_{0110- \operatorname{lowbit}0110}(0100) $,再减的话就为0了,所以就OK了。 - 单点查询 ,跟上面差不多,就是用$C_{i}$的值减去$ C_{i - \operatorname {lowbit}i} $ 再减去 $C_{(i - \operatorname {lowbit}i) - \operatorname {lowbit}(i - \operatorname {lowbit}i)} \cdots$。 P.S. 跟上面差不多,就不仔细说了。 P.S. $ \operatorname {lowbit} i $的实现是 $i&(-i)$,用了计算机内部补码的性质 ~~受了k总的影响~~,题解不发代码,只要能帮助别人,就是一篇合格的题解!