Go语言视频零基础入门到精通

javalearner

(一） 什么是树状数组？
    树状数组用来求区间元素和，求一次区间元素和的时间效率为O(logn)。     有些同学会觉得很奇怪。用一个数组S保存序列A[]的前i个元素和，那么求区间i,j的元素和不就为S[j]-S[i-1]，那么时间效率为O(1)，岂不是更快？ 但是，如果题目的A[]会改变呢？例如：
我们来定义下列问题，我们有n个盒子。可能的两个操作为：
1.向盒子k添加石块
2.查询从盒子i到盒子j总的石块数    自然的解法带有对操作1为O(1)而对操作2为O(n)的时间复杂度。但是用树状数组，对操作1和2的时间复杂度都为O(logn)。 （二) 图解树状数组C[]
   现在来说明下树状数组是什么东西？假设序列为A[1]~A[8]  
  
   
   

     
   

     
   
  



网络上面都有上图，但是我将这个图做了2点改进。 （1）图中有一棵满二叉树，满二叉树的每一个结点对应A[]中的一个元素。
（2）C为A对应的那一列的最高的节点。 现在告诉你：序列C[]就是树状数组。那么C[]如何求得？
C[1]=A[1];
C[2]=A[1]+A[2];
C[3]=A[3];
C[4]=A[1]+A[2]+A[3]+A[4];
C[5]=A[5];
C[6]=A[5]+A[6];
C[7]=A[7];
C[8]= A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7]+A[8]; 以上只是枚举了所有的情况，那么推广到一般情况，得到一个C的抽象定义：
     因为A[]中的每个元素对应满二叉树的每个叶子，所以我们干脆把A[]中的每个元素当成叶子，那么：C=C的所有叶子的和。 现在不得不引出关于二进制的一个规律：先仔细看下图： 将十进制化成二进制，然后观察这些二进制数最右边1的位置：
1 --> 00000001
2 --> 00000010
3 --> 00000011
4 --> 00000100
5 --> 00000101
6 --> 00000110
7 --> 00000111
8 --> 00001000 1的位置其实从我画的满二叉树中就可以看出来。但是这与C[]有什么关系呢？接下来的这部分内容很重要： 在满二叉树中，
以1结尾的那些结点（C[1],C[3],C[5],C[7]），其叶子数有1个，所以这些结点C代表区间范围为1的元素和；
以10结尾的那些结点（C[2],C[6]），其叶子数为2个，所以这些结点C代表区间范围为2的元素和；
以100结尾的那些结点（C[4]），其叶子数为4个，所以这些结点C代表区间范围为4的元素和；
以1000结尾的那些结点（C[8]），其叶子数为8个，所以这些结点C代表区间范围为8的元素和。
扩展到一般情况：    i 的二进制中的从右往左数有连续的x个“0”，那么拥有2^x个叶子，为序列A[]中的第i-2^x+1到第i个元素的和。
终于，我们得到了一个C的具体定义：
C=A[i-2^x+1]+…+A，其中x为i 的二进制数中的从右往左数有连续“0”的个数。(i>=1)

(三)C展开以后有多少项？由下面公式计算：

1. int lowbit(int t){//计算c[t]展开的项数   
   
2.    return t&(-t);   
   
3.   }   
   
4.   
   
5. 例：   
   
6. lowbit(1)=1   C1 = A1   
   
7. lowbit(2)=2   C2 = A1 + A2   
   
8. lowbit(3)=1   C3 = A3   
   
9. lowbit(4)=4   C4 = A1 + A2 + A3 + A4   
   
10. lowbit(5)=1   C5 = A5   
    
11. lowbit(6)=2   C6 = A5 + A6   
    
12. lowbit(7)=1   C7 = A7   
    
13. lowbit(8)=8   C8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8   
    
14. .......   
    
15. c[t]展开的项数就是lowbit(t),c[t]就是从a[t]开始往左连续求lowbit(t)个数的和，   
    
16.   
    
17.   
    
18. lowbit(1)=1       lowbit(2)=2       lowbit(3)=1      lowbit(4)=4  
    
19. lowbit(5)=1       lowbit(6)=2       lowbit(7)=1      lowbit(8)=8  
    
20. lowbit(9)=1      lowbit(10)=2      lowbit(11)=1      lowbit(12)=4  
    
21. lowbit(13)=1      lowbit(14)=2      lowbit(15)=1      lowbit(16)=16  
    
22. lowbit(17)=1      lowbit(18)=2      lowbit(19)=1      lowbit(20)=4  
    
23. lowbit(21)=1      lowbit(22)=2      lowbit(23)=1      lowbit(24)=8  
    
24. lowbit(25)=1      lowbit(26)=2      lowbit(27)=1      lowbit(28)=4  
    
25. lowbit(29)=1      lowbit(30)=2      lowbit(31)=1      lowbit(32)=32  
    
26. lowbit(33)=1      lowbit(34)=2      lowbit(35)=1      lowbit(36)=4  
    
27. lowbit(37)=1      lowbit(38)=2      lowbit(39)=1      lowbit(40)=8  
    
28. lowbit(41)=1      lowbit(42)=2      lowbit(43)=1      lowbit(44)=4  
    
29. lowbit(45)=1      lowbit(46)=2      lowbit(47)=1      lowbit(48)=16  
    
30. lowbit(49)=1      lowbit(50)=2      lowbit(51)=1      lowbit(52)=4  
    
31. lowbit(53)=1      lowbit(54)=2      lowbit(55)=1      lowbit(56)=8  
    
32. lowbit(57)=1      lowbit(58)=2      lowbit(59)=1      lowbit(60)=4  
    
33. lowbit(61)=1      lowbit(62)=2      lowbit(63)=1      lowbit(64)=64  
    

复制代码

(四) 修改
    当我们修改A的值时，可以从C往根节点一路上溯，调整这条路上的所有C[]即可，对于节点i，父节点下标 p=i+lowbit(i)

1. //增加某个元素的大小,给某个节点 i 加上 x   
   
2. update(int i,int x){   
   
3. while(i<=n){   
   
4.     c[i]=c[i]+x;   
   
5.     i=i+lowbit(i);   
   
6.      }   
   
7. }   
   

复制代码

(五) 利用树状数组求前i个元素的和S[n]
   理解了C[n]后，前n个元素的和S[n]就很容易实现。 只需找到n以前的所有最大子树，把其根节点的C加起来即可。

我们拿一个具体的实例来看：
S[7]=C[7]+C[6]+C[4]
因为C[7]=A[7]，C[6]=A[6]+A[5]，C[4]=A[4]+A[3]+A[2]+A[1]，所以S[7]=C[7]+C[6]+C[4]

1. int Sum(int n) //求前n项的和.   从下标1开始
   
2. {   
   
3.     int sum=0;   
   
4.     while(n>0)   
   
5.     {   
   
6.          sum+=c[n];   
   
7.          n=n-lowbit(n);   
   
8.     }        
   
9.     return sum;   
   
10. }   
    

复制代码

(六)测试

1. 例：   
   
2. public class TreeArray{   
   
3.        int n;//数组元素个数   
   
4.        int[] a;//原数组   
   
5.        int[] c;//对应的树状数组   
   
6.   
   
7.   public TreeArray(int[] a){   
   
8.        n=a.length;   
   
9.        this.a=a;   
   
10.        c=new int[a.length];   
    
11.        for(int i=1;i< a.length;i++){   //从下标1开始
    
12.            for(int j=0;j< lowbit(i);j++)   
    
13.              c[i]=c[i]+a[i-j];   
    
14.        }   
    
15.   }   
    
16.   
    
17.   
    
18.   private int lowbit(int t){//计算c[t]展开的项数   
    
19.    return t&(-t);   
    
20.   }   
    
21.       
    
22.   private void update(int i,int x){   
    
23.       while(i<=n){   
    
24.         c[i]=c[i]+x;   
    
25.         i=i+lowbit(i);   
    
26.      }   
    
27.     }   
    
28.   
    
29.   private int Sum(int k){ //求前k项的和.   从下标1开始
    
30.    int sum=0;   
    
31.     while(k>0){   
    
32.        sum+=c[k];   
    
33.        k=k-lowbit(k);   
    
34.     }        
    
35.     return sum;   
    
36.   }   
    
37.   
    
38.     public static void main(String args[]){   
    
39.        int a[]={0,1,2,3,4,5,6,7,8,9,10};   //从下标1开始
    
40.        TreeArray ta=new TreeArray(a);   
    
41.        System.out.println(ta.Sum(10));   
    
42.         ta.update(5,-20);   
    
43.        System.out.println(ta.Sum(10));   
    
44.        System.out.println(ta.Sum(4));   
    
45.   
    
46.     }   
    
47. }   
    
48.       
    
49. 运行：   
    
50. C:java>java   TreeArray   
    
51. 55  
    
52. 35  
    
53. 10     
    

复制代码

  
  
   
   

     
   

     
   
  

复制代码