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

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

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

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

#defineLLlonglong //單個(gè)修改 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ū)間查詢代碼實(shí)現(xiàn)：

//單個(gè)查詢 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ù)組主要應(yīng)用于區(qū)間操作，相比起線段樹來說，代碼實(shí)現(xiàn)簡單太多了，而且效率也很高，非常值得研究掌握。 審核編輯 ：李倩