题解 P2068 【统计和】
Suuon_Kanderu
2020-03-12 17:45:04
树状数组是一种用来维护区间操作的数据结构
如图,一个维护和的一个树状数组。
因为直接看十进制看不出什么套路,好心的我转换成了二进制。
你可以清晰的发现很多性质,下面我来捋一捋:
![](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总的影响~~,题解不发代码,只要能帮助别人,就是一篇合格的题解!