树状数组

别人实在讲得很清楚了，参考自 http://blog.csdn.net/ljd4305/article/details/10101535

再说一些，树状数组本质还是单点更新区间求和

更新的时候可以看这个例子   0101 -> 0110 -> 1000 结合更新函数和树状数组那个图应该很好理解，其实就是从当前节点一直向父节点更新

至于求和的时候也是一样假设求1~i的和，i的二进制表示从低位到高位第一个不为零的为第k+1位，那么就加上c[k]，表示将原a[]数组的i~i-2^k+1个数全加了，然后对比函数接下来自然从i-2^k再开始加，重复上述操作直至为零，附带模版

更新

void add(int k , int num) 
{ 
    while(k <= n) 
    { 
          tree[k] += num; 
          k += k&(-k); 
    } 
} 

求和

int Sum(int k) 
{ 
    int sum = 0; 
    while(k > 0) 
    { 
        sum += tree[k]; 
        k -= k&(-k); 
    } 
    return sum; 
}

顺便推荐树状数组一些运用  http://www.cnblogs.com/wenruo/p/5787418.html