這里的文章寫得不錯：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; }新聞熱點
疑難解答
