简介

关于定义,参见Wiki:Binary Indexed Tree 中文名:二叉索引树
很好,那么我今天想讲一讲它是用来做什么的。(很激动吧!),首先在此我要感谢GGN小同学因为我请他喝了一瓶可乐而特地花了很长时间为我讲解这个BIT,让我理解的很深刻,所以呢,我特地也为大家分享一下二叉索引树的故事。

那么,问题来了 树状数组是什么东西呢

您一定听说过数组的对吧,学过数据结构的也一定知道树这种东西,那么我们可以很玄学的将数组和树结合到一起,让它们杂交生成子一代(扯多了)—— 树状数组(即二叉索引树 BIT)

其实,如果叫它 “二叉索引树” ,您就会感受到它的妙处了!

首先,要为大家讲解为什么我说二叉索引树很神奇!
相比于小根堆,我觉得二叉索引树的性质更加的玄妙,对于某一个非叶子结点,其左右子结点编号是这个结点的2倍和2倍加1,堆满足的操作如下

build:建立一个空堆;
insert:向堆中插入一个新元素;
update:将新元素提升使其符合堆的性质;
get:获取当前堆顶元素的值;
delete:删除堆顶元素;
heapify:使删除堆顶元素的堆再次成为堆。

和二叉索引树名字很接近的又一个东西叫做二叉搜索树 BST但是二者有着本质上的区别哦。

下面我们来讲BIT是怎么工作的:

与二进制的关系

您会注意到有一个奇怪的东西叫做

lowbit < i >

这是啥?很显然,它叫做lowbit ~~废话~~,那么我们仔细看 “bit” 那个单词,会不会联想到 “位运算” 呢?那么 “low” 又有什么含义呢?

前方高能预警

以十进制正整数 10492 为例
掏出计算器开始邪恶的按下去

🤔诶,注意观察 10492 的二进制数位

0010 1000 1111 1100

好,到此您可能还是没有看出来什么,那么我把 10492 按位取反之后得到了十进制数 ***** (管它是多少呢) ,其实我们应该更着重看一下二进制位:

1101 0111 0000 0011

很显然这是按位取反的性质,哦对了顺便提一下,在C语言里按位取反是这个可爱的小符号 ‘~’(自带蠢萌)这个先搁在这里,我问大家一个问题:

知道负整数的二进制怎么求吗?

假设有一个 int 类型的数,值为5,那么,我们知道它在计算机中表示为:

0000 0000 0000 0101

那么-5该怎么转化成二进制数呢?
在计算机中,负数以原码的补码形式表达
什么叫补码呢?这得从原码,反码说起。

原码: 一个正数,按照绝对值大小转换成的二进制数;一个负数按照绝对值大小转换成的二进制数,然后最高位补1,称为原码。比如:

0000 0000 0000 0101 是5的原码
0000 0000 0000 0101 是-5的原码  

反码: 正数的反码与原码相同,负数的反码为对该数的原码除符号位外各位取反。比如:

正数 0000 0000 0000 0101
反码 0000 0000 0000 0101
负数 0000 0000 0000 0101
反码 1111 1111 1111 1010

补码: 正数的补码与原码相同,负数的补码为对该数的原码除符号位外各位取反,然后在最后一位加1。比如:

负数 0000 0000 0000 0101
反码 1111 1111 1111 1010
补码 1111 1111 1111 1011

可以看出来区别了吧,那么求-5的二进制编码,其实就是求其按位取反后,在最后一位加上一个小’1’,当然如果最后一位是’1’记得进位哦。

那么对于 10492 取其相反数,再计算:

因为10492的相反数在二进制编码中最高位达到了2^63 故输出的十进制数不是-10492也很好理解,可以类比int类型溢出(当然,这里明显的是long long)注意看二进制码的区别:

0010 1000 1111 1100
1101 0111 0000 0100

不要着急问为什么最后两位是相同的呢

原码: 0010 1000 1111 1100
补码: 1101 0111 0000 0011
相反数 1101 0111 0000 0100

因为0011+1=0100(进位了)

可是此处的进位只是巧合吗?

我们为什么不利用它呢?

因为构建BIT是需要2^n 作为索引去维护此结点的前缀区间,那么这个点一定是很特殊的!

所以说来说去,lowbit之所以称为lowbit,就是因为lowbit为此整型数的二进制最低位1的位置

再理解一下:low (最低) bit (1位)

接下来是个问题,我们怎么求lowbit?
先给出代码,请您理解一番:

int lowbit(int x){
    return x&-x;
}

好啦,您觉得是开玩笑?这么复杂的过程,就这么一点代码,好欺骗感情啊。好的,如果您觉得是这样的话:请把它背下来吧!甚至不需要动您的十二指肠就能想出来的:

x 和 -x 取一个按位与

正文

废话不多说,您现在已经解锁了求lowbit成就,通过观察,不难发现,我可以有两个操作:

求区间和
更改结点数值

对于区间求和,我们可以用索引结点去维护区间和。换句话说,就是我把每个结点上都存入从这个结点到达它上一个同级lowbit节点的2倍位置的原数组的区间总和。

比如对于数组编号4的点对应的 lowbit(4)=4 ,那么对于索引点4(图中用绿色笔记标记)它的值为“1+2+3+4=10”,同理对于编号12对应的 lowbit(12)=4 的点,它存放的值为“9+10+11+12=42”,很简单对吧!

构建成树:

从编号为7的点开始,每次求对于7的前导:

7 ~ 6 ~ 4 ~ 0 这几个索引点所维护的值(也就是这几个点的值,还记得这几个点的值是它所包含的区间内所有数的和)之和,举个栗子:7 ~ 6 ~ 4 ~ 0 这段过程就是在求:(7)+(5+6)+(1+2+3+4)=28,此处注意我加括号的位置哦。

如果您看明白了,就会很好理解一下这段求区间和的代码了

int sum(int x){
    int s=0;
    while(x>0){
     s+=C[x];
     x-=lowbit(x);//精髓在此
    }
    return s;
}

对于更改(增删或修改)数组的值
先上代码:

void add(int x,int d){
    a[x]+=d;//对于原数组进行更改
    while(x<=n){
        c[x]+=d;
        x+=lowbit(x);
    }
}

很明显的啦对于插入区间值:

3 ~ 4 ~ 8 ~ 16 注意以下我说的值都是索引结点:在3中增加一个数n,那么4中也要加上n,8中也要加上n。

看图道理就很好理解了

img

所以这两个就是BIT中最基本的操作函数,大家都掌握了吗?
可以去看看这个讲解,我认为还是讲的很明白的
戳我进入 – 树状数组入门分享

好啦今天就讲到这里吧,还有不明白的小伙伴们可以在下方评论区评论哦。这是我写的第一篇教程,希望大家能采纳,如果有不当的地方,一定要和我说哦,非常欢迎大家评论。希望我的博客能被大家支持。ありがとうみんな!

分类: Algorithm

发表评论

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.