首页 > 代码库 > POJ 2309 BST(树状数组Lowbit)

POJ 2309 BST(树状数组Lowbit)

题意是给你一个满二叉树,给一个数字,求以这个数为根的树中最大值和最小值。

 

理解树状数组中的lowbit的用法。

说这个之前我先说个叫lowbit的东西,lowbit(k)就是把k的二进制的高位1全部清空,只留下最低位的1,比如10的二进制是1010,则lowbit(k)=lowbit(1010)=0010(2进制),介于这个lowbit在下面会经常用到,这里给一个非常方便的实现方式,比较普遍的方法lowbit(k)=k&-k,这是位运算,我们知道一个数加一个负号是把这个数的二进制取反+1,如-10的二进制就是-1010=0101+1=0110(负数的二进制表示就是正数二进制的补码),然后用1010&0110,答案就是0010了!明白了求解lowbit的方法就可以了,继续下面。介于下面讨论十进制已经没有意义(这个世界本来就是二进制的,人非要主观的构建一个十进制),下面所有的数没有特别说明都当作二进制。

目前的个人理解就是 lowbit 求出来的是这个根的管辖区域。

代码:

 1 #include <stdio.h>  
 2   
 3 int lowbit(int n)  
 4 {  
 5     return n & (-n);  
 6 }  
 7   
 8 int main()  
 9 {  
10     int ncase;  
11     scanf("%d", &ncase);  
12     while (ncase--)  
13     {  
14         int k;  
15         scanf("%d", &k);  
16         printf("%d %d\n", k - lowbit(k) + 1, k + lowbit(k) - 1);  
17     }  
18     return 0;  
19 }  

 

POJ 2309 BST(树状数组Lowbit)