線段樹(shù)從零開(kāi)始

By 巖之痕

一：為什么需要線段樹(shù)？

題目一：

10000個(gè)正整數(shù)，編號(hào)1到10000，用A[1],A[2],A[10000]表示。

修改：無(wú)

統(tǒng)計(jì)：1.編號(hào)從L到R的所有數(shù)之和為多少？ 其中1<= L <= R <= 10000.

方法一：對(duì)于統(tǒng)計(jì)L,R ，需要求下標(biāo)從L到R的所有數(shù)的和，從L到R的所有下標(biāo)記做[L..R],問(wèn)題就是對(duì)A[L..R]進(jìn)行求和。

這樣求和，對(duì)于每個(gè)詢問(wèn)，需要將(R-L+1)個(gè)數(shù)相加。

方法二：更快的方法是求前綴和,令 S[0]=0, S[k]=A[1..k] ，那么，A[L..R]的和就等于S[R]-S[L-1]，

這樣，對(duì)于每個(gè)詢問(wèn)，就只需要做一次減法，大大提高效率。

題目二：

10000個(gè)正整數(shù)，編號(hào)從1到10000，用A[1],A[2],A[10000]表示。

修改：1.將第L個(gè)數(shù)增加C （1 <= L <= 10000）

統(tǒng)計(jì)：1.編號(hào)從L到R的所有數(shù)之和為多少？ 其中1<= L <= R <= 10000.

再使用方法二的話，假如A[L]+=C之后，S[L],S[L+1],,S[R]都需要增加C,全部都要修改，見(jiàn)下表。

方法一 方法二

A[L]+=C 修改1個(gè)元素 修改R-L+1個(gè)元素

求和A[L..R] 計(jì)算R-L+1個(gè)元素之和 計(jì)算兩個(gè)元素之差

從上表可以看出，方法一修改快，求和慢。 方法二求和快，修改慢。

那有沒(méi)有一種結(jié)構(gòu)，修改和求和都比較快呢？答案當(dāng)然是線段樹(shù)。

二：線段樹(shù)的點(diǎn)修改

上面的問(wèn)題二就是典型的線段樹(shù)點(diǎn)修改。

線段樹(shù)先將區(qū)間[1..10000]分成不超過(guò)4*10000個(gè)子區(qū)間，對(duì)于每個(gè)子區(qū)間，記錄一段連續(xù)數(shù)字的和。

之后，任意給定區(qū)間[L,R]，線段樹(shù)在上述子區(qū)間中選擇約2*log2(R-L+1)個(gè)拼成區(qū)間[L,R]。

如果A[L]+=C ，線段樹(shù)的子區(qū)間中，約有l(wèi)og2(10000)個(gè)包含了L，所以需要修改log2(10000)個(gè)。

于是，使用線段樹(shù)的話，

A[L]+=C 需要修改log2(10000) 個(gè)元素

求和A[L...R]需要修改2*log2(R-L+1) <= 2 * log2(10000) 個(gè)元素。

log2(10000) < 14 所以相對(duì)來(lái)說(shuō)線段樹(shù)的修改和操作都比較快。

問(wèn)題一：開(kāi)始的子區(qū)間是怎么分的？

首先是講原始子區(qū)間的分解，假定給定區(qū)間[L,R]，只要L < R ，線段樹(shù)就會(huì)把它繼續(xù)分裂成兩個(gè)區(qū)間。

首先計(jì)算 M = (L+R)/2，左子區(qū)間為[L,M]，右子區(qū)間為[M+1,R]，然后如果子區(qū)間不滿足條件就遞歸分解。

以區(qū)間[1..13]的分解為例，分解結(jié)果見(jiàn)下圖：

問(wèn)題二：給定區(qū)間【L,R】，如何分解成上述給定的區(qū)間？

對(duì)于給定區(qū)間[2,12]要如何分解成上述區(qū)間呢？

分解方法一：自下而上合并——利于理解

先考慮樹(shù)的最下層，將所有在區(qū)間[2,12]內(nèi)的點(diǎn)選中，然后，若相鄰的點(diǎn)的直接父節(jié)點(diǎn)是同一個(gè)，那么就用這個(gè)父節(jié)點(diǎn)代替這兩個(gè)節(jié)點(diǎn)（父節(jié)點(diǎn)在上一層）。這樣操作之后，本層最多剩下兩個(gè)節(jié)點(diǎn)。若最左側(cè)被選中的節(jié)點(diǎn)是它父節(jié)點(diǎn)的右子樹(shù)，那么這個(gè)節(jié)點(diǎn)會(huì)被剩下。若最右側(cè)被選中的節(jié)點(diǎn)是它的父節(jié)點(diǎn)的左子樹(shù)，那么這個(gè)節(jié)點(diǎn)會(huì)被剩下。中間的所有節(jié)點(diǎn)都被父節(jié)點(diǎn)取代。對(duì)最下層處理完之后，考慮它的上一層，繼續(xù)進(jìn)行同樣的處理。

下圖為n=13的線段樹(shù)，區(qū)間[2,12]，按照上面的敘述進(jìn)行操作的過(guò)程圖：

由圖可以看出：在n=13的線段樹(shù)中，[2,12]=[2] + [3,4] + [5,7] + [8,10] + [11,12] 。

分解方法二：自上而下分解——利于計(jì)算

首先對(duì)于區(qū)間[1,13]，計(jì)算(1+13)/2 = 7，于是將區(qū)間[2,12]“切割”成了[2,7]和[8,12]。

其中[2,7]處于節(jié)點(diǎn)[1,7]的位置，[2,7] < [1,7] 所以繼續(xù)分解，計(jì)算(1+7)/2 = 4, 于是將[2,7] 切割成[2,4]和[5,7]。

[5,7]處于節(jié)點(diǎn)[5,7]的位置，所以不用繼續(xù)分解，[2,4]處于區(qū)間[1,4]的位置，所以繼續(xù)分解成[2]和[3,4]。

最后【2】 < 【1,2】，所以計(jì)算(1+2)/2=1 ，將【2】用1切割，左側(cè)為空，右側(cè)為【2】

當(dāng)然程序是遞歸計(jì)算的，不是一層一層計(jì)算的，上圖只表示計(jì)算方法，不代表計(jì)算順序。

問(wèn)題三：如何進(jìn)行區(qū)間統(tǒng)計(jì)？

假設(shè)這13個(gè)數(shù)為1,2,3,4,1,2,3,4,1,2,3,4,1. 在區(qū)間之后標(biāo)上該區(qū)間的數(shù)字之和：

如果要計(jì)算[2,12]的和，按照之前的算法：

[2,12]=[2] + [3,4] + [5,7] + [8,10] + [11,12]

  29 = 2 + 7 + 6 + 7 + 7

計(jì)算5個(gè)數(shù)的和就可以算出[2,12]的值。

問(wèn)題四：如何進(jìn)行點(diǎn)修改？

假設(shè)把A[6]+=7 ,看看哪些區(qū)間需要修改？[6],[5,6],[5,7],[1,7],[1,13]這些區(qū)間全部都需要+7.其余所有區(qū)間都不用動(dòng)。

于是，這顆線段樹(shù)中，點(diǎn)修改最多修改5個(gè)線段樹(shù)元素（每層一個(gè)）。

下圖中，修改后的元素用藍(lán)色表示。

問(wèn)題五：存儲(chǔ)結(jié)構(gòu)是怎樣的？

線段樹(shù)是一種二叉樹(shù)，當(dāng)然可以像一般的樹(shù)那樣寫成結(jié)構(gòu)體，指針什么的。

但是它的優(yōu)點(diǎn)是，它也可以用數(shù)組來(lái)實(shí)現(xiàn)樹(shù)形結(jié)構(gòu)，可以大大簡(jiǎn)化代碼。

數(shù)組形式適合在編程競(jìng)賽中使用，在已經(jīng)知道線段樹(shù)的最大規(guī)模的情況下，直接開(kāi)足夠空間的數(shù)組，然后在上面建立線段樹(shù)。

怎么用數(shù)組來(lái)表示一顆二叉樹(shù)呢？假設(shè)某個(gè)節(jié)點(diǎn)的編號(hào)為v,那么它的左子節(jié)點(diǎn)編號(hào)為2*v，右子節(jié)點(diǎn)編號(hào)為2*v+1。

然后規(guī)定根節(jié)點(diǎn)為1.這樣一顆二叉樹(shù)就構(gòu)造完成了。通常2*v在代碼中寫成 v<<1 。 2*v+1寫成 v<<1|1 。

問(wèn)題六：代碼中如何實(shí)現(xiàn)？

(0)定義：

#define maxn 100007 //元素總個(gè)數(shù)  

int Sum[maxn<<2];//Sum求和  

int A[maxn],n;//存原數(shù)組數(shù)據(jù)下標(biāo)[1,n]   

(1)建樹(shù)：

//PushUp函數(shù)更新節(jié)點(diǎn)信息 ，這里是求和  

void PushUp(int rt){Sum[rt]=Sum[rt<<1]+Sum[rt<<1|1];}  

//Build函數(shù)建樹(shù)   

void Build(int l,int r,int rt){ //l,r表示當(dāng)前節(jié)點(diǎn)區(qū)間，rt表示當(dāng)前節(jié)點(diǎn)編號(hào)  

    if(l==r) {//若到達(dá)葉節(jié)點(diǎn)   

        Sum[rt]=A[l];//儲(chǔ)存數(shù)組值   

        return;  

    }  

    int m=(l+r)>>1;  

    //左右遞歸   

    Build(l,m,rt<<1);  

    Build(m+1,r,rt<<1|1);  

    //更新信息   

    PushUp(rt);  

}  

(2)點(diǎn)修改：

假設(shè)A[L]+=C:

void Update(int L,int C,int l,int r,int rt){//l,r表示當(dāng)前節(jié)點(diǎn)區(qū)間，rt表示當(dāng)前節(jié)點(diǎn)編號(hào)  

    if(l==r){//到葉節(jié)點(diǎn)，修改   

        Sum[rt]+=C;  

        return;  

    }  

    int m=(l+r)>>1;  

    //根據(jù)條件判斷往左子樹(shù)調(diào)用還是往右   

    if(L <= m) Update(L,C,l,m,rt<<1);  

    else Update(L,C,m+1,r,rt<<1|1);  

    PushUp(rt);//子節(jié)點(diǎn)更新了，所以本節(jié)點(diǎn)也需要更新信息   

}   

點(diǎn)修改其實(shí)可以寫的更簡(jiǎn)單，只需要把一路經(jīng)過(guò)的Sum都+=C就行了，不過(guò)上面的代碼更加規(guī)范，在題目更加復(fù)雜的時(shí)候，按照格式寫更不容易錯(cuò)。

(3)區(qū)間查詢（本題為求和）：

詢問(wèn)A[L..R]的和

注意到，整個(gè)函數(shù)的遞歸過(guò)程中，L,R是不變的。

首先如果當(dāng)前區(qū)間[l,r]在[L,R]內(nèi)部，就直接累加答案

如果左子區(qū)間與[L,R]有重疊，就遞歸左子樹(shù)，右子樹(shù)同理。

int Query(int L,int R,int l,int r,int rt){//L,R表示操作區(qū)間，l,r表示當(dāng)前節(jié)點(diǎn)區(qū)間，rt表示當(dāng)前節(jié)點(diǎn)編號(hào)  

    if(L <= l && r <= R){  

        //在區(qū)間內(nèi)，直接返回   

        return Sum[rt];  

    }  

    int m=(l+r)>>1;  

    //左子區(qū)間:[l,m] 右子區(qū)間：[m+1,r] 求和區(qū)間:[L,R]

    //累計(jì)答案  

    int ANS=0;  

    if(L <= m) ANS+=Query(L,R,l,m,rt<<1);//左子區(qū)間與[L,R]有重疊，遞歸

    if(R > m) ANS+=Query(L,R,m+1,r,rt<<1|1); //右子區(qū)間與[L,R]有重疊，遞歸

    return ANS;  

}