01 故事起源有N個數(shù)排列成一排，如何快速進行區(qū)間修改與求和呢？ ? ?02 分析首先最容易想到的方法就是先求出前綴和sum[i]，然后區(qū)間[a,b]的和就可以直接通過sum[b]-sum[a-1]得到。 ?但如果要對數(shù)組進行修改，就會有一些問題。比如對a[3]加1，則下面對應的sum[3],sum[4],sum[5]都需要進行修改，這個效率就很低了。 ?原因在于sum[i]是前面區(qū)間[1,i]中所有元素的和，所以修改任何一個元素，則后面的sum[i]都得重新計算。 那能不能找到一種間斷式的前綴和呢，只需要統(tǒng)計前面區(qū)間中的部分元素。這樣在修改某個a[i]的時候就不會影響后面的所有sum[i]。 ?其實就是要找到這樣的一種映射關系，既能統(tǒng)計出前綴和，還可以提高修改的效率。sum[i]以前是統(tǒng)計區(qū)間[1,i]所有的i個元素，而現(xiàn)在是統(tǒng)計區(qū)間[1,i]中的k個元素。 ?樹狀數(shù)組其實就是這樣的一種映射。 03 定義樹狀數(shù)組是按下面這種對應關系來計算前面若干元素的和，但直接看可能還看不出來規(guī)律。 ?先把元素的下標1、2、3...轉(zhuǎn)成二進制。 ?再把每個二進制數(shù)，從右向左，截取到第一個1的位置。截取的二進制數(shù)也會對應一個十進制數(shù)。 ?比如12對應的二進制數(shù)為1100，截取的二進制數(shù)為100，而100轉(zhuǎn)為十進制為4。所以我們可以定義這樣一種運算，lowbit(12)=4。 ? ?那這個lowbit要如何快速計算呢？ 計算機原理中，首先我們知道有原碼，反碼，補碼。最高位為符號位，0為正數(shù)，1為負數(shù)。正數(shù)的三碼相同，負數(shù)的反碼是符號位不變，其余位取反，而補碼則是反碼加1。在計算機中負數(shù)是以補碼的方式存儲的。 然后再看下面的12和-12，補碼進行位與操作時，就正好是lowbit運算。 代碼實現(xiàn)：

intlowbit(intx){ returnx&-x; } 把上面的對應位置的lowbit都計算出來再觀察，可以發(fā)現(xiàn)lowbit的數(shù)值正好就是sum[i]統(tǒng)計的元素個數(shù)。 ?總結(jié)一般的規(guī)律如下： sum[i]等于區(qū)間[i-lowbit(i)+1,i]中所有元素的和。也就是從位置i開始，往前數(shù)lowbit(i)個元素，加起來就是sum[i]。 ? ?04 規(guī)律lowbit(i)對應的數(shù)一定是1，2，4...，因為截取的二進制為1000...。根據(jù)lowbit(i)可以先對sum[i]進行分層。 ?而sum[i]元素也有一種包含關系，再把包含關系提上來。 ?sum[i]就是前面連續(xù)的lowbit(i)個元素的和，直接展開更清晰。紅色矩形就是下面覆蓋的藍色小方塊的和。 ?紅色是sum數(shù)組，藍色是a數(shù)組，再觀察下標之間的關系。 ? ?05 單點修改例如修改a[2]，因為sum[2],sum[4]都包含了a[2]，所以對應都要修改。 ?如果修改a[3]，因為sum[3],sum[4]都包含了a[3]，所以對應都要修改。 ?觀察發(fā)現(xiàn)，修改一個元素a[i]時，sum[i]是一層一層的向上進行修改，上一層的下標正好是當前層的下標i加上lowbit(i)。 代碼實現(xiàn)：

voidadd(intindex,intx){ while(index<=?n)?{ ????????sum[index]?+=?x; ????????index?+=?lowbit(index); ????} } ? ?06 區(qū)間查詢例如查詢區(qū)間[1,5]，需要統(tǒng)計sum[5],sum[4]。 ?如果查詢區(qū)間[1,3]，需要統(tǒng)計sum[3],sum[2]。 ?觀察發(fā)現(xiàn)，查詢區(qū)間[1,i]的前綴和時，是一段一段往前查詢的，下一段的下標正好是當前段的下標i減去lowbit(i)。 代碼實現(xiàn)：

intquery(intindex){ intret=0; while(index>0){ ret+=sum[index]; index-=lowbit(index); } returnret; } 如此，就可以輕松搞定單點修改及區(qū)間查詢了，但最開始的問題是區(qū)間修改，這個又該如何實現(xiàn)呢？ 07 區(qū)間修改首先得引入一個差分數(shù)組d[i]，d[i]=a[i]-a[i-1]。 ?對數(shù)組d[i]計算前綴和，又可以還原為原數(shù)組元素a[i]。 ?通過公式替換，原數(shù)組的前綴和sum[i]也可以通過d[i]來得到。 ?展開來看就是這樣。 ?通過觀察，可以對上面公式作如下變形。其中最關鍵的是sigma(d[j])和sigma(d[j]*j)。 ?如果維護d[i]和d[i]*i兩個數(shù)組的前綴和，就可以快速得到sum[k]。 ?當對區(qū)間[3,5]增加2時，因為d[i]是差分數(shù)組，所以只需要對d[3]增加2，對d[6]減去2即可。同理e[i]數(shù)組，只需要e[3]增加2*3，對e[6]減去2*6。 ?一般規(guī)律如下： 代碼實現(xiàn)：

#defineLLlonglong //單個修改 voidadd(LL*sum,LLindex,LLx){ while(index<=?n)?{ ????????sum[index]?+=?x; ????????index?+=?lowbit(index); ????} } //區(qū)間修改 voidrange_add(LLleft,LLright,LLx){ right++; add(sum1,left,x); add(sum1,right,-x); add(sum2,left,x*left); add(sum2,right,-x*right); } 08 區(qū)間查詢代碼實現(xiàn)：

//單個查詢 LLquery(constLL*sum,LLindex){ LLret=0; while(index>0){ ret+=sum[index]; index-=lowbit(index); } returnret; } //區(qū)間查詢 LLrange_query(LLleft,LLright){ left--; LLsumA=(left+1)*query(sum1,left)-query(sum2,left); LLsumB=(right+1)*query(sum1,right)-query(sum2,right); returnsumB-sumA; } 09 總結(jié)樹狀數(shù)組主要應用于區(qū)間操作，相比起線段樹來說，代碼實現(xiàn)簡單太多了，而且效率也很高，非常值得研究掌握。 審核編輯 ：李倩