树状数组

基本概念

Binary Indexed Tree
二叉索引树
它的查询和修改的时间复杂度都是log(n)，空间复杂度则为O(n).

二进制操作

如上图所示,可以写出下列式子:
C1 = A1
C2 = A1 + A2
C3 = A3
C4 = A1 + A2 + A3 + A4
C5 = A5
C6 = A5 + A6
C7 = A7
C8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8
...
C16 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8 + A9 + A10 + A11 + A12 + A13 + A14 + A15 + A16

Ci有自己的管辖区域,
这需要看Ci化成二进制后后面有多少个零,
那么这个节点管辖的区间为2^k(2的k次方)
但是要想求最后有多少个零要怎么求呢?不急,现在就是二进制使用的时候了.

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

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

这两种是求二进制的补码,再进行与操作,最后的出结果.

单点修改

当我们要对最底层的值进行更新时，那么它相应的父亲节点存储的和也需要进行更新

    void update(int x,int val){
          while(x<MAX){
            tree[x] = val;
            x += lowbit(x);
          }
      }

区间查询

查询的时候，则需要向前进行统计

    int add(int x){
        int sum = 0;
        while(x>0){
            sum+=tree[x];
            x -= lowbit(x);
        }
        return sum;
    }

其实树状数组里面更多的是二进制的理解,只要理解,就可以很快的掌握这些.

hdu 1541 数星星
就是一道模板题.

C++

    #include <iostream>
    #include <cstring>
    #define N 32005
    using namespace std;

    int tree[N],in[N],n;
    int lowbit(int x){
       return x&(-x);
    }

    void update(int x){
        while(x<N){
            tree[x]++;
            x+=lowbit(x);
        }
    }

    int add(int x){
        int sum = 0;
        while(x>0){
            sum+=tree[x];
            x -= lowbit(x);
        }
        return sum;
    }

    int main(){
        while(cin>>n){
            memset(tree,0,sizeof(tree));
            memset(in,0,sizeof(in));
            for(int i=0;i<n;i++){
                int x,y;
                cin>>x>>y;
                in[add(x+1)]++;
                update(x+1);
            }
            for(int i=0;i<n;i++){
                cout<<in[i]<<endl;
            }
        }
        return 0;
    }