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

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

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

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

#defineLLlonglong //單個修改 voidadd(LL*sum,LLindex,LLx){ while(index<=?n)?{ ????????sum[index]?+=?x; ????????index?+=?lowbit(index); ????} } //區間修改 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 區間查詢代碼實現：

//單個查詢 LLquery(constLL*sum,LLindex){ LLret=0; while(index>0){ ret+=sum[index]; index-=lowbit(index); } returnret; } //區間查詢 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 總結樹狀數組主要應用于區間操作，相比起線段樹來說，代碼實現簡單太多了，而且效率也很高，非常值得研究掌握。 審核編輯 ：李倩