Binary Index Tree 树状数组总结


初步搞懂树状数组
树状数组用来求区间元素和,求一次区间元素和的时间效率为O(logn)。
    有些同学会觉得很奇怪。用一个数组S[i]保存序列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)。



网络上面都有上图,但是我将这个图做了2点改进。
(1)图中有一棵满二叉树,满二叉树的每一个结点对应A[]中的一个元素。
(2)C[i]为A[i]对应的那一列的最高的节点。
现在告诉你:序列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];

现在不得不引出关于二进制的一个规律:先仔细看下图:
将十进制化成二进制,然后观察这些二进制数最右边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[i]代表区间范围为1的元素和;
以10结尾的那些结点(C[2],C[6]),其叶子数为2个,所以这些结点C[i]代表区间范围为2的元素和;
以100结尾的那些结点(C[4]),其叶子数为4个,所以这些结点C[i]代表区间范围为4的元素和;
以1000结尾的那些结点(C[8]),其叶子数为8个,所以这些结点C[i]代表区间范围为8的元素和。
扩展到一般情况:
   i 的二进制中的从右往左数有连续的x个“0”,那么拥有2^x个叶子,为序列A[]中的第i-2^x+1到第i个元素的和。
终于,我们得到了一个C[i]的具体定义:
C[i]=A[i-2^x+1]+…+A[i],其中x为i 的二进制数中的从右往左数有连续“0”的个数。(i>=1)

http://www.cnblogs.com/huangxincheng/archive/2012/12/05/2802858.html
展现了位运算与数组结合的神奇魅力
之所以采用这样的分布方式,是因为我们使用的是这样的一个公式:S[i]=a[i-2k+1]+....+a[i]。
其中:2k 中的k表示当前S[i]在树中的层数,它的值就是i的二进制中末尾连续0的个数,2k也就是表示S[i]中包含了哪些a[],
举个例子:  i=610=0110;可以发现末尾连续的0有一个,即k=1,则说明S[6]是在树中的第二层,并且S[6]中有21项,随后我们求出了起始项:
            a[6-21+1]=a[5],但是在编码中求出k的值还是有点麻烦的,所以我们采用更灵巧的Lowbit技术,即:2k=i&-i 。
           则:S[6]=a[6-21+1]=a[6-(6&-6)+1]=a[5]+a[6]。
分离出最后的1
注意: 最后的1表示一个整数的二进制表示中,从左向右数最后的那个1。
由于我们经常需要将一个二进制数的最后的1提取出来,因此采用一种高效的方式来做这件 事是十分有必要的。令num是我们要操作的整数。在二进制表示中,num可以记为a1b, a代表最后的1前面的二进制数码,由于a1b中的1代表的是从左向右的最后一个1, 因此b全为0,当然b也可以不存在。比如说13=1101,这里最后的1右边没有0,所以b不存在。
我们知道,对一个数取负等价于对该数的二进制表示取反加1。所以-num等于(a1b)^- +1= a^- 0b^- +1。由于b全是0,所以b^- 全为1。最后,我们得到:
-num=(a1b)^- +1=a^- 0b^- +1=a^- 0(1…1)+1=a^- 1(0…0)=a^- 1b
现在,我们可以通过与操作(在C++,java中符号为&)将num中最后的1分离出来:
num & -num = a1b & a^- 1b = (0…0)1(0…0)

int lowbit(int t){//计算c[t]展开的项数   
   return t&(-t);   
  }   
  
例:   
lowbit(1)=1   C1 = A1   
lowbit(2)=2   C2 = A1 + A2   
lowbit(3)=1   C3 = A3   
lowbit(4)=4   C4 = A1 + A2 + A3 + A4   
lowbit(5)=1   C5 = A5   
lowbit(6)=2   C6 = A5 + A6   
lowbit(7)=1   C7 = A7   
lowbit(8)=8   C8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8   
.......   
c[t]展开的项数就是lowbit(t),c[t]就是从a[t]开始往左连续求lowbit(t)个数的和, 

 public class TreeArray{   
       int n;//数组元素个数   
       int[] a;//原数组   
       int[] c;//对应的树状数组   
  
  public TreeArray(int[] a){   
       n=a.length;   
       this.a=a;   
       c=new int[a.length];   
       for(int i=1;i< a.length;i++){   //从下标1开始
           for(int j=0;j< lowbit(i);j++)   
             c[i]=c[i]+a[i-j];   
       }   
  }   
  
  
  private int lowbit(int t){//计算c[t]展开的项数   
   return t&(-t);   
  }   
      
  private void update(int i,int x){    
      while(i<=n){    
        c[i]=c[i]+x;    
        i=i+lowbit(i);    
     }    
    }    
  
  private int Sum(int k){ //求前k项的和.   从下标1开始
   int sum=0;    
    while(k>0){    
       sum+=c[k];    
       k=k-lowbit(k);    
    }        
    return sum;    
  }    
  
    public static void main(String args[]){   
       int a[]={0,1,2,3,4,5,6,7,8,9,10};   //从下标1开始
       TreeArray ta=new TreeArray(a);   
       System.out.println(ta.Sum(10));   
        ta.update(5,-20);   
       System.out.println(ta.Sum(10));   
       System.out.println(ta.Sum(4));   
  
    }   
 }   
http://blog.csdn.net/chenguolinblog/article/details/10050049
                                   
                  
1 一维树状数组
  1 什么是树状数组
       树状数组是一个查询和修改复杂度都为log(n)的数据结构,假设数组A[1..n],那么查询A[1]+...+A[n]的时,间是log级别的,而且是一个在线的数据结构。

  2 树状数组作用
       我们经常会遇到动态连续和查询问题,给定n个元素A[1~N],让我们求sum[L,R] = A[L]+...+A[R],或者更改A[i]的值。
       假设数据很小的时候,那么我们利用暴力就可以搞定,这个时候更改A[i]的复杂度为O(1),但是求和的复杂度为O(n),如果有m次求和就是O(n*m),但是m很大的时候这个方法显然是不能够满足效率的要求。这个时候我们引入树状数组,树状数组的求和和更新都是O(logN),所以大大的降低了复杂度。

  3 具体分析
     1 建立树状数组就是先把A[] 和 C[]清空,然后假设有n个数那么就是做n次的update()操作就是建立树状数组,所以总的时间复杂度为O(nlogn)。
     2 设原数组为A[1..N],树状数组为c[1..N],其中c[k] = A[k-(2^t)+1] + ... + A[k]。比如c[6] = A[5] + A[6]。
        假设 A为被计数数组,C为树状数组(计数)
        0000 0001:C1 = A1
        0000 0010:C2 = A1 + A2
        0000 0011:C3 = A3
        0000 0100:C4 = A1 + A2 + A3 + A4
        0000 0101:C5 = A5
        0000 0110:C6 = A5 + A6
        0000 0111:C7 = A7
        0000 1000:C8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8
        ...
        0001 0000:C16 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8+ A9 + A10 + A11 + A12 + A13 + A14 + A15+ A16

     3 也就是说,把k表示成二进制1***10000,那么c[k]就是A[1***00001] + A[1***00010] + ... + A[1***10000] 这一段数的和。

     4 设一个函数lowbit(k)为取得k的最低非零位,容易发现,根据上面的表示方法,从A[1]到A[k]的所有数的总和即为
        sum[k] = c[k] + c[k-lowestbit(k)] + c[k-lowestbit(k)-lowestbit(k-lowestbit(k))] + ... 于是可以在logk的时间内求出sum[k]。

     5 当数组中某元素发生变化时,需要改动的c值是c[k],c[k+lowestbit(k)], c[k+lowestbit(k)+lowestbit(k+lowestbit(k))] ... 这个复杂度是logN (N为最大范围)

     6 如果题目要求sum[L , R] = sum[R]-sum[L-1]
        sum[L-1] = A[1]+A[2]+...+A[L-1]
        sum[R] = A[1]+A[2]+...+A[L]+...+A[R]
        sum[R]-sum[L-1] = A[L]+A[L+2]+...+A[R]

     7 树状数组的下标严格从1开始,所以如果出现0的情况要注意加1.(因为lowbit(0)是0所以如果出现为0的时候会进入无限循环中) , 树状数组中的每个元素至少含有它本身的一个值。


2 二维树状数组
   1 二维树状数组说白了就是每一维都是树状数组
      问题:一个由数字构成的大矩阵,能进行两种操作
                1 对矩阵里的某个数加上一个整数(可正可负)
                2 查询某个子矩阵里所有数字的和,要求对每次查询,输出结果。

   2 一维树状数组很容易扩展到二维,在二维情况下:数组A[][]的树状数组定义为:
     C[x][y] = ∑ a[i][j], 其中,x-lowbit(x) + 1 <= i <= x , y-lowbit(y) + 1 <= j <= y.

   3 例:举个例子来看看C[][]的组成。
             设原始二维数组为:
          A[][]={{a11,a12,a13,a14,a15,a16,a17,a18,a19},
                       {a21,a22,a23,a24,a25,a26,a27,a28,a29},
                       {a31,a32,a33,a34,a35,a36,a37,a38,a39},
                       {a41,a42,a43,a44,a45,a46,a47,a48,a49}};
             那么它对应的二维树状数组C[][]呢?

      记:
             B[1]={a11,a11+a12,a13,a11+a12+a13+a14,a15,a15+a16,...} 这是第一行的一维树状数组
             B[2]={a21,a21+a22,a23,a21+a22+a23+a24,a25,a25+a26,...} 这是第二行的一维树状数组
             B[3]={a31,a31+a32,a33,a31+a32+a33+a34,a35,a35+a36,...} 这是第三行的一维树状数组
             B[4]={a41,a41+a42,a43,a41+a42+a43+a44,a45,a45+a46,...} 这是第四行的一维树状数组

      那么:
             C[1][1] = a11 , C[1][2] = a11+a12 , C[1][3] = a13 , C[1][4] = a11 + a12 + a13 + a14 , c[1][5]=a15.这是A[][]第一行的一维树状数组

              C[2][1] = a11 + a21 , C[2][2] = a11 + a12 + a21 + a22 , C[2][3] = a13 + a23 , C[2][4] = a11 + a12 + a13 + a14 + a21 + a22 + a23 + a24 这是A[][]数组第一行与第二行相加后的树状数组

              C[3][1] = a31 , C[3][2] = a31 + a32 , C[3][3] = a33 , C[3][4] = a31 + a32 + a33 + a34 , C[3][5] = a35 , C[3][6]=a35+a36,...这是A[][]第三行的一维树状数组

              C[4][1] = a11 + a21 + a31 + a41 , C[4][2] = a11 + a12 + a21 + a22 + a31 + a32 + a41 + a42 ,这是A[][]数组第一行+第二行+第三行+第四行后的树状数组


3  树状数组的两类操作
    1 单点更新,区间求和
       1 一维树状数组,单点更新,区间求和
       比如要更新点x ,x点的值加上val即调用add(x , val) , 求区间[1 , x]的和即为getSum(x)
 
int lowbit(int x){
    return x&(-x);
}

int getSum(int x){
    int sum = 0;
    while(x){
        sum += treeNum[x];
        x -= lowbit(x);
    }
    return sum;
}

void add(int x , int val){
    while(x < MAXN){
         treeNum[x] += val;
         x += lowbit(x);
    }
}
            2 二维树状数组,单点更新,区间求和
       比如要更新点(x , y) ,(x , y)点的值加上val即调用add(x , y , val) , 求矩形[1 , 1] - [x , y]的和即为getSum(x , y)
            
            如上图求矩形的面积为getSum(x2 , y2)-getSum(x1-1,y2)-getSum(x2,y1-1)+getSum(x1-1 , y1-1)
           
int lowbit(int x){
    return x&(-x);
}

int getSum(int x , int y){
    int sum = 0;
    for(int i = x ; i > 0 ; i -= lowbit(i))
       for(int j = y ; j > 0 ; j -= lowbit(j))
           sum += treeNum[i][j];
    return sum;
}

void add(int x , int y , int val){
    for(int i = x ; i < MAXN ; i += lowbit(i))
       for(int j = y ; j < MAXN ; j += lowbit(j))
           treeNum[i][j] += val;
}


    2 区间更新,单点求和  
         1 一维树状数组
        更改区间[x , y],区间[x , y]里面的每个数全部加上val , 查询点k的值
        区间[x , y]加上val相当于点x加上val , 点y+1减去val,那么求k点的值就等于[1,k]的和
            
int lowbit(int x){
    return x&(-x);
}

int getSum(int x){
    int sum = 0;
    while(x){
        sum += treeNum[x];
        x -= lowbit(x);
    }
    return sum;
}

void add(int x , int val){
    while(x < MAXN){
         treeNum[x] += val;
         x += lowbit(x);
    }
}

void solve(){
    // 把区间[x , y]每一点加上val
    add(x , val);
    add(y+1 , -val);
    // 计算点k的值
    int num = getSum(k);
}


         2 二维树状数组
     更改矩形[x1 , y1] - [x2 , y2],[x1 , y1] - [x2 , y2]里面的每个数全部加上val , 查询点(x , y)的值
          
          矩形[x1 , y1] - [x2 , y2]里面的每一个元素加上val相当于点(x1 , y1)加上val , 点(x1 , y2+1)减去val,点(x2+1 , y1)减去val , 点(x2+1 , y2+1)加上val那么求某个点(x , y)的值即求[1 , 1] - [x , y]的和
           
int lowbit(int x){
    return x&(-x);
}

int getSum(int x , int y){
    int sum = 0;
    for(int i = x ; i > 0 ; i -= lowbit(i))
       for(int j = y ; j > 0 ; j -= lowbit(j))
           sum += treeNum[i][j];
    return sum;
}

void add(int x , int y , int val){
    for(int i = x ; i < MAXN ; i += lowbit(i))
       for(int j = y ; j < MAXN ; j += lowbit(j))
           treeNum[i][j] += val;
}

void solve(){
     // 矩形[x1 , y1]-[x2 , y2]每个点加上val
     add(x1 , y1 , val); 
     add(x2+1 , y1 , -val); 
     add(x1 , y2+1 , -val); 
     add(x2+1 , y2+1 , val); 
     // 求点(x , y)的值
     int num = getSum(x , y);
}



5 常用的技巧
   假设初始化数组每个点的值为1,那么我们知道对于一维的树状数组来说,我们知道treeNum[i] = lowbit(i) . 对于二维树状数组来说treeNum[i][j] = lowbit(i)*lowbit(j)
    
void init(){
    // 一维
    memset(treeNum , 0 , sizeof(treeNum));
    for(int i = 1 ; i < MAXN ; i++){
        num[i] =1;
        treeNum[i] = lowbit(i);
    }
    
    // 二维
    memset(treeNum , 0 , sizeof(treeNum));
    for(int i = 1 ; i < MAXN ; i++){
       for(int j = 1 ; j < MAXN ; j++){
           num[i][j] = 1;
           treeNum[i][j] = lowbit(i)*lowbit(j);
       }
    }
}
Read full article from 初步搞懂树状数组

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts