这里的文章写得不错：http://blog.csdn.net/int64ago/article/details/7429868
从这张图片可以看出树状数组是一个二分的思想。那么它的本质是什么呢？其实是二进制数。例如6如果用二进制数来表示6=0110=4+2 , 13=1101=8+4+1 . 因此我们可以用一个c[]数组来表示管辖范围，c[13]=c[8]+c[4]+c[1]. 那么求1~13的和就不用a[1]+a[2]+…a[13]了，而是可以直接c[8]+c[4]+c[1]。
我们可以看出刚才的13是1101有8,4,1构成，倒序来写就是13=1+4+8。我们可以先把1减掉，12=4+8，再把4减掉,8=8,再把8减掉8-8=0.这样一步一步求和运算。对应的1，4，8就是末尾1对应的位置，也就是大牛博客里讲到的Lowbit=x & (-x).这里不赘言。
那么如何能把a[]数组转换为c[]数组呢？这里给大家一种构造，就是每个c[i]管辖的范围就是lowbit(i).比如c[6]的管辖范围是2,原因是lowbit(6)=0010,保留最后一个1。那么什么样的子节点对父节点有影响。其实就是它加上它的lowbit.相当于二分(形象的讲是镜像)，把它另一边的数加上就是它的父节点。例如4的管辖范围为4，相当于二分镜像的另一边管辖范围，加上自己的节点标号就是父节点的值8。再如10的父节点是12.那么10管辖的范围应该是2，其实也就相当于二分镜像的另一边管辖范围，加上就是父节点的值。
lowbit//-x=取反+1
int lowbit(int x){ return x&(-x);}构建父节点c[]
void update(int p,int x) { while(p<=n) { c[p]+=x; p+=lowbit(p); } }区间求和
int sum(int p) { int sum=0; while(p>0) { sum+=c[p]; p-=lowbit(p); } return sum; }新闻热点
疑难解答
