树状数组

  所谓的树状数组，其实就是跟线段数差不多的东西，只不过两者表示方法不一样罢了

 线段数每个节点表示（l,r）这一段的数据，表示范围较广，树状数组也差不多，只不过其a[i]表示范围为（i-2^k+1, i）的数据，k为i2进制下末尾的0的个数，表示范围较少。。

 线段数一般来说一段插入，一段查询，树状数组一般就是点插入，一段查询，，，

百度文库有很详细的讲解http://wenku.baidu.com/view/3ffb717f5acfa1c7aa00ccb0.html

一维树状数组code核心代码：

int lowbit(int t){ return t & (-t); } //计算t末尾的0的个数，也可以用 t&(t ^ (t -1)) 的表达式求

void updata(int k, int data){  //插入点（往其父节点更新）
    for (int i = k; i <= n; i += lowbit(i))
      sum[i] += data;
}

int getsum(int k){ //求和（往前，其并列节点）
    int ret = 0;
    for (int i = k; i > 0; i -= lowbit(i))
        ret += sum[i];
    return ret;
}

二维线段数的话，其实上原理差不多，就多了重循环

http://www.java3z.com/cwbwebhome/article/article1/1369.html?id=4804这个博客讲的很清楚

核心code（几乎与1维的一模一样）：

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

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

}

void updata(int x, int y, int data){
    for (int i = x; i < MXN; i += lowbit(i))
        for (int j = y; j < MXN; j += lowbit(j))
            sum[i][j] += data;

}