树状数组 介绍

闲话

这篇文章一时兴起想更,所以时断时续更新一点。
 

正题

理解树状数组需要理解前缀和或者分治这种东西,当然这是特别基础的东西。
下面两张图是树状数组的实例,大家也都能看出一点点的规律。
shu1

shu2

树状数组的核心是lowbit。lowbit的功能是取到一个数最低位的1。换句话说lowbit(k)就是把k的二进制的高位1全部清空,只留下最低的1。比如10的二进制是1010,则lowbit(k)=lowbit(1010)=0010(2进制)。其实每一个n,都预处理好n到n前lowbit(n)个数的子段和。如果要整段求[l, r]和,转换成求(0,l-1]和(0,r]的和,然后分成小的子段和来求解。

 

Lowbit

lowbit有很多种写法,比如:

更常见的是

常见的是利用机器码的特性。一个数取负,相当于把这个数取反,然后加上1,两个数取与,就能把最后一个1给取出来。

 

求和与更新

求和就是不断的分成子段和。每次取出最后一个1,加到答案上,再去掉,不断这么操作,知道全部加完。
我的写法是直接把lowbit写进了for循环,代码:

 
至于更新,和求和的过程正好相反,不断加上最后一个1,然后直到超出需要维护的上限。具体看代码:

 

其他

个人还是觉得树状数组是一个非常美的数据结构,是对二进制很好的体现。所以学习树状数组的时候最好要自己在草稿纸上用二进制进行模拟。或者是看下下面这篇文章,文章链接,是非常不错的。

 

例题

题目链接,CodeVS1080,题目是最基本的RMQ问题,单点修改区间查询。来训练线段树和树状数组都不错。
直接上代码,写的比较丑。

 

未完结

发表评论

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