本文部分轉(zhuǎn)載自：https://blog.csdn.net/iwts_24/article/details/81484561

區(qū)間求和問題-醫(yī)院賣藥

? ? ? ? 假設(shè)有一家醫(yī)院，醫(yī)院有賣藥的地方，不同的藥品有不同的數(shù)量。每次開藥、進(jìn)藥都要在計(jì)算機(jī)里面記錄數(shù)量變化，這樣方便醫(yī)院的管理。那么我們?cè)撊绾螌?shí)現(xiàn)這樣的程序？當(dāng)然，藥品數(shù)量的儲(chǔ)存用數(shù)組是比較合適的（真實(shí)的項(xiàng)目當(dāng)然要用數(shù)據(jù)庫）

int a[8] = {1,2,3,4,5,6,7,8};

現(xiàn)在，給出指令，第1號(hào)到第7號(hào)，這7個(gè)藥品的數(shù)量全部加8，那么代碼實(shí)現(xiàn)就是標(biāo)準(zhǔn)的for循環(huán)了：

for(int i = 0;i < 7;i++){a[i] += 8; }

同樣，如果進(jìn)藥，仍然循環(huán)即可。所以對(duì)于區(qū)間數(shù)量的變化，時(shí)間復(fù)雜度為O(n)

? ? ? ? 那么現(xiàn)在我們需要算所有藥品的數(shù)量，最簡單的方法仍然是for循環(huán)：

1 int sum = 0; 2 for(int i = 0;i < 8;i++){ 3 sum += a[i]; 4 }

?

這樣，就算我們提高要求，求出區(qū)間[a,b]之間的和，仍然遍歷即可，算法復(fù)雜度為O(b-a)

? ? ? ? 看起來，我們對(duì)于區(qū)間的操作，無論是求和還是數(shù)據(jù)修改，都能在線性的時(shí)間段內(nèi)完成。但是這樣的時(shí)間復(fù)雜度其實(shí)并不好。一般來說，比賽中數(shù)據(jù)量1000000就差不多了，但是我們的操作數(shù)量可是非常多的。這樣的數(shù)據(jù)范圍：有m個(gè)數(shù)據(jù)0<m<=1000000，有n次操作0<n<10000。那么這樣，就算是線性的時(shí)間復(fù)雜度仍然有超時(shí)的可能。

? ? ? ? 所以，我們就需要用線段樹這樣的數(shù)據(jù)結(jié)構(gòu)來儲(chǔ)存數(shù)據(jù)，從而降低操作的時(shí)間復(fù)雜度。

什么是線段樹

? ? ? ? 線段樹的主要思想是二分，也就是通過二分的方法來查找節(jié)點(diǎn)。首先看一下線段樹的圖的表示（這里用了百度百科的圖）

? ? ? ? 實(shí)際上，這是數(shù)據(jù)為8的線段樹。藍(lán)色的標(biāo)記是二叉樹的節(jié)點(diǎn)編號(hào)，最下面的紅色的框體框住的8個(gè)葉子就是實(shí)際上數(shù)據(jù)存放的位置。而節(jié)點(diǎn)內(nèi)部寫的區(qū)間，就是指數(shù)據(jù)存放區(qū)間的和。例如2號(hào)節(jié)點(diǎn)，里面區(qū)間是[1,4]也就是1號(hào)到4號(hào)之間的數(shù)據(jù)的和。

線段樹的操作-建樹

? ? ? ? 基本的線段樹就如上圖所示，那么我們首先應(yīng)該基于一段數(shù)據(jù)進(jìn)行建樹操作。可以看出，線段樹是非常耗費(fèi)空間的。所以我們不管是用結(jié)構(gòu)體還是數(shù)組，在表示線段樹的時(shí)候都要在數(shù)據(jù)量n的情況下多開更大的空間。一般都是開四倍。所以基本的聲明與初始化如下：

1 #define MAX 2333 2 3 int tree[4*MAX]; 4 5 void init() 6 { 7 memset(tree,0,sizeof(tree)); 8 memset(lz, 0, sizeof(lz)); 9 }

　　?

然后就是建樹了，我們需要將數(shù)組變成一個(gè)樹。代碼如下：

1 void build(int node, int l, int r) 2 { 3 if(l == r) // 到達(dá)葉子節(jié)點(diǎn)，賦值 4 { 5 scanf("%d", &tree[node]); 6 return; 7 } 8 9 int mid = (l+r)/2; 10 build(node*2, l, mid); 11 build(node*2+1, mid+1, r); 12 13 tree[node] = tree[node*2] + tree[node*2+1]; 14 }

?

?

? ? ? ? 這樣的建樹，是一個(gè)遞歸的過程。l與r分別表示區(qū)間，結(jié)合上面的圖，當(dāng)l==r的時(shí)候說明遞歸已經(jīng)遍歷到葉子節(jié)點(diǎn)了，而這個(gè)節(jié)點(diǎn)node也是二叉樹的節(jié)點(diǎn)編號(hào)。對(duì)應(yīng)了數(shù)組的下標(biāo)。所以進(jìn)行賦值。然后直接return進(jìn)行回溯。那么在正常遞歸的時(shí)候，我們需要利用二叉樹的性質(zhì)，即對(duì)于node編號(hào)的節(jié)點(diǎn)而言，左子樹編號(hào)為2*node，右子樹為2*node+1。同樣，由于二分的性質(zhì)，利用mid = (l+r)/2，就可以獲取下一個(gè)子樹的區(qū)間范圍。

? ? ? ? 在回溯的時(shí)候，是從樹的最下層開始向最上層回溯，那么同樣利用二叉樹的性質(zhì)，我們可以輕松將子樹的數(shù)據(jù)加到父節(jié)點(diǎn)上。這樣，當(dāng)函數(shù)完成的時(shí)候，我們就可以利用數(shù)組來構(gòu)建了一個(gè)線段樹。

線段樹的操作-單點(diǎn)修改

? ? ? ? 線段樹并不必須要進(jìn)行區(qū)間的操作，如果是對(duì)單點(diǎn)進(jìn)行操作，完全可以用更快的方法來實(shí)現(xiàn)。而對(duì)于單點(diǎn)修改而言，其實(shí)相比區(qū)間修改的代碼要簡單很多（因?yàn)閘azy數(shù)組的存在），所以能用針對(duì)單點(diǎn)的修改最好不要用區(qū)間修改。單點(diǎn)更新非常類似二分查找，通過遞歸找到更新點(diǎn)的位置，在回溯的時(shí)候更新所有節(jié)點(diǎn)的值。代碼：

?

1 // 單點(diǎn)更新，node為1(從根節(jié)點(diǎn)開始)，lr為根節(jié)點(diǎn)的區(qū)間，index為更新點(diǎn)，n為更新值 2 void update(int node,int l,int r,int index,int n) 3 { 4 if(l == r) 5 { 6 tree[node] += n; // 更新方式，可以自由改動(dòng) 7 return; 8 } 9 int mid = (l+r) / 2; 10 // push_down(node,mid-l+1,r-mid); 若既有點(diǎn)更新又有區(qū)間更新，需要這句話 11 if(index <= mid) 12 update(n,index,l,mid,node*2); 13 else 14 update(n,index,mid+1,r,node*2+1); 15 tree[node] = tree[node*2] + tree[node*2 + 1]; // 回溯過程，需要將線段樹上層數(shù)據(jù)更新 16 }

?

? ? ? ? l與r就是指當(dāng)前節(jié)點(diǎn)的區(qū)間范圍，剛開始肯定是填1,8了，因?yàn)榫€段樹的最上邊節(jié)點(diǎn)代表的范圍（參照上圖的白色區(qū)間字體）就是1,8。那么，如果l==r，就說明到達(dá)了葉子節(jié)點(diǎn)，當(dāng)然就是需要更新的節(jié)點(diǎn)了。如何進(jìn)入遞歸？就跟二分一樣，index與mid進(jìn)行判斷，看是走左子樹還是右子樹。最后一定不要忘記回溯，因?yàn)槿~子節(jié)點(diǎn)更新后，上層節(jié)點(diǎn)的值也需要更新，這樣才算維護(hù)了線段樹。

? ? ? ? 里面有一行注釋的代碼，這里需要把后面的懶惰標(biāo)記、區(qū)間操作學(xué)完才能理解。現(xiàn)在就當(dāng)不存在吧。

懶惰標(biāo)記

? ? ? ? 在進(jìn)行區(qū)間操作之前，要首先理解線段樹的懶惰標(biāo)記，試想，我們?cè)诓僮鞯臅r(shí)候有可能有這樣的操作。首先進(jìn)行區(qū)間修改，修改了800次，然后再進(jìn)行一次查詢。這樣，如果我們每次都將整個(gè)線段樹的數(shù)據(jù)進(jìn)行更新，實(shí)際上是非常慢的，如果我們能用一段空間，來記錄修改數(shù)據(jù)，只有在使用的時(shí)候，一次性更新，就非常的方便。

? ? ? ? 所以這也是懶惰標(biāo)記的作用。可以先對(duì)修改的數(shù)據(jù)進(jìn)行儲(chǔ)存，只有在使用的時(shí)候才更新線段樹。那么，理論上我們應(yīng)該建一個(gè)跟線段樹同樣大小的數(shù)組，稱為懶惰數(shù)組，表示了每個(gè)節(jié)點(diǎn)的懶惰標(biāo)記。有這樣的操作：

1.修改數(shù)據(jù)的時(shí)候，每次遞歸到某節(jié)點(diǎn)，修改數(shù)據(jù)以后將數(shù)據(jù)的變化添加到數(shù)組中。

2.當(dāng)使用到這個(gè)節(jié)點(diǎn)的時(shí)候，發(fā)現(xiàn)對(duì)應(yīng)的懶惰標(biāo)記存在，那么就應(yīng)該更新該節(jié)點(diǎn)，以及以下的所有節(jié)點(diǎn)的數(shù)據(jù)，方便使用。

總之，就是不使用的時(shí)候就一直在積累，在使用的時(shí)候再統(tǒng)一更新。

? ? ? ? 那么懶惰數(shù)組的更新非常簡單，對(duì)線段樹更新的時(shí)候就可以添加到懶惰標(biāo)記，但是在使用的時(shí)候，我們需要用一個(gè)函數(shù)來完成懶惰標(biāo)記的下傳操作，也就是更新積累的值。代碼：

1 void push_down(int node, int l, int r) 2 { 3 if(lz[node]) 4 { 5 int mid = (l+r)/2; 6 lz[node*2] += lz[node]; 7 lz[node*2+1] += lz[node]; 8 tree[node*2] += (mid-l+1)*lz[node]; 9 tree[node*2+1] += (r-mid)*lz[node]; 10 lz[node] = 0; 11 } 12 }

? ? ? ? lz數(shù)組，即lazy，就是懶惰標(biāo)記數(shù)組。可以看出，當(dāng)lz[node]存在值的時(shí)候，就說明現(xiàn)在我在使用這個(gè)節(jié)點(diǎn)，而這個(gè)節(jié)點(diǎn)以及其下的節(jié)點(diǎn)需要更新了，所以就利用二叉樹的性質(zhì)向下傳遞更新數(shù)據(jù)，同時(shí)更新線段樹中的數(shù)據(jù)。最終，要將該節(jié)點(diǎn)的懶惰標(biāo)記清零。

? ? ? ? 注意，下推的時(shí)候不是一直更新到葉子節(jié)點(diǎn)，而是只更新當(dāng)前節(jié)點(diǎn)以及2個(gè)子樹，因?yàn)閷?shí)際操作的時(shí)候，只要碰到對(duì)某節(jié)點(diǎn)的操作就要調(diào)用push_down()函數(shù)，所以每次只用下推一層即可。

? ? ? ? push_down()函數(shù)的使用需要在下面的區(qū)間操作中添加。

線段樹的操作-區(qū)間更新

? ? ? ? 單點(diǎn)更新類似二分查找，更新的時(shí)候?qū)?jīng)過的路徑進(jìn)行操作就可以了。但是區(qū)間更新需要考慮整個(gè)區(qū)間。線段樹除了葉子節(jié)點(diǎn)，都表示了一段區(qū)間的值，那么就要配合懶惰標(biāo)記在整個(gè)區(qū)間上進(jìn)行操作。先看代碼：

1 // 區(qū)間更新，lr為更新范圍，LR為線段樹范圍，add為更新值 2 void update_range(int node, int l, int r, int L, int R, int add) 3 { 4 if(l <= L && r >= R) 5 { 6 lz[node] += add; 7 tree[node] += (R-L+1)*add; // 更新方式 8 return; 9 } 10 11 push_down(node, L, R); 12 int mid = (L+R)/2; 13 if(mid >= l) // 進(jìn)入左子樹 14 update_range(node*2, l, r, L, mid, add); 15 if(r > mid) // 進(jìn)入右子樹 16 update_range(node*2+1, l, r, mid+1, R, add); 17 18 tree[node] = tree[node*2] + tree[node*2 + 1]; 19 }

? ? ? ? 仍然以[1,8]區(qū)間的線段樹為例，修改[1,6]的區(qū)間，使區(qū)間內(nèi)的數(shù)據(jù)全部加1。那么我們可以在線段樹圖的基礎(chǔ)上手動(dòng)走一遍這個(gè)代碼，來理解線段樹的區(qū)間操作以及與懶惰標(biāo)記的配合。

?

?

?

?

這個(gè)是一個(gè)線段樹，現(xiàn)在我們需要對(duì)[1,6]范圍內(nèi)進(jìn)行加一，那么就應(yīng)該這樣：

update_range(1,1,6,1,8,1); // 從結(jié)點(diǎn)1，即最上邊開始
? ? ? ? 我們手動(dòng)走一遍上述代碼，首先，if判斷不成立。這個(gè)if判斷主要判定的是區(qū)間，我們每次遞歸進(jìn)入函數(shù)，操作區(qū)間與當(dāng)前結(jié)點(diǎn)表示區(qū)間總共有2種可能：

1.操作區(qū)間完全與結(jié)點(diǎn)表示區(qū)間重合。此時(shí)，說明我們已經(jīng)可以對(duì)該結(jié)點(diǎn)進(jìn)行操作了。

2.操作區(qū)間在結(jié)點(diǎn)表示區(qū)間內(nèi)。此時(shí)，說明現(xiàn)在的結(jié)點(diǎn)表示空間太大了，需要向下尋找更合適的區(qū)間。

3.操作區(qū)間比結(jié)點(diǎn)表示區(qū)間大，只有向下推的時(shí)候才能出現(xiàn)這樣的情況，跟第一種可能的結(jié)果一樣，對(duì)結(jié)點(diǎn)進(jìn)行操作就行了。

4.操作區(qū)間與結(jié)點(diǎn)表去區(qū)間只有一部分重合。只有向下推的時(shí)候才能出現(xiàn)這樣的情況，跟第二種可能的結(jié)果一樣，下推。

5.操作區(qū)間與結(jié)點(diǎn)表示區(qū)間完全不重合。無操作，等待程序自己結(jié)束。

其他可能是不存在的，例如操作區(qū)間大于結(jié)點(diǎn)表示區(qū)間。因?yàn)椴僮鲄^(qū)間最大不可能超過線段樹的區(qū)間，所以越分越小的情況下，最少就是跟結(jié)點(diǎn)表示區(qū)間一致。

? ? ? ? 所以，這個(gè)if，就是判斷操作區(qū)間與結(jié)點(diǎn)表示區(qū)間滿足什么條件。接著上例，[1,6]與[1,8]相比，明顯是第二種情況，所以需要向下推移。此時(shí)，由于開始接觸下面的結(jié)點(diǎn)了，所以需要調(diào)用push_down，進(jìn)行懶惰標(biāo)記向下推移，保證接觸的是數(shù)據(jù)已經(jīng)修改過的結(jié)點(diǎn)。然后當(dāng)然是區(qū)分左子樹右子樹了，2種可能，進(jìn)入左子樹或右子樹。

? ? ? ? 首先是進(jìn)入左子樹的情況，此時(shí)操作區(qū)間仍然是[1,6]，而結(jié)點(diǎn)表示區(qū)間是[1,4]出現(xiàn)了情況3。此時(shí)，說明[1,4]區(qū)間的所有數(shù)據(jù)都要變化。這也進(jìn)入了if判斷之中。不要擔(dān)心[5,6]區(qū)間，這一部分已經(jīng)遞歸進(jìn)入右子樹了。此時(shí)，在該結(jié)點(diǎn)處更新懶惰標(biāo)記與數(shù)據(jù)信息。注意這句代碼：

tree[node] += 1LL*(R - L + 1)*add;
[1,4]結(jié)點(diǎn)存放的是1-4的數(shù)據(jù)，所以每個(gè)數(shù)據(jù)+1，這個(gè)結(jié)點(diǎn)就要+4。同時(shí)，我們已經(jīng)標(biāo)記懶惰標(biāo)記了，所以直接return。下面的結(jié)點(diǎn)全部不更新，等到需要的時(shí)候在下推就行了。至此，左子樹的遞歸就完成了。return后回溯，此時(shí)進(jìn)入右子樹的遞歸。

? ? ? ? 進(jìn)入右子樹，此時(shí)操作區(qū)間仍然是[1,6]，而結(jié)點(diǎn)表示區(qū)間則變成了[5,8]，是情況4，所以仍然下推。這時(shí)候，左子樹變成[5,6]，右子樹變成[7,8]。左子樹變成情況1了，那么就進(jìn)行更新。右子樹已經(jīng)完全脫離區(qū)間，所以不用管，等他自己遞歸完成后沒有任何操作地結(jié)束吧。

? ? ? ? 注意，程序的最后還有回溯這個(gè)過程。確實(shí)，我們的操作因?yàn)閼卸钄?shù)組是不再向下傳遞了。但是已經(jīng)更新的結(jié)點(diǎn)需要在回溯的時(shí)候向上更新。由于剛開始，我們就是從結(jié)點(diǎn)1開始的，所以回溯一定能將更新結(jié)點(diǎn)之前的結(jié)點(diǎn)全部更新。

? ? ? ? 最后得到的圖如下：

?

?

?

?

紅字就是更新的結(jié)點(diǎn)，而旁邊標(biāo)記的紅色的1就是懶惰標(biāo)記。下次調(diào)用有懶惰標(biāo)記的結(jié)點(diǎn)就會(huì)導(dǎo)致更新與向下傳遞懶惰標(biāo)記。這樣，我們就完成了區(qū)間更新的操作。

? ? ? ? 所以，這里有最最最重要的一點(diǎn)：由于懶惰標(biāo)記，所以很多數(shù)據(jù)是沒有變化的。如果在一次區(qū)間更新后就需要調(diào)用真實(shí)數(shù)據(jù)，那么應(yīng)該先向下更新全部數(shù)據(jù)后再調(diào)用。否則得到的數(shù)據(jù)是未更新的錯(cuò)誤數(shù)據(jù)。這樣，我們也能理解單點(diǎn)操作的那一行注釋的代碼了，其實(shí)就是下推懶惰標(biāo)記。因?yàn)橹灰褂昧藚^(qū)間操作，就有可能有懶惰標(biāo)記產(chǎn)生。所以需要使用push_down()來下推。

線段樹的操作-區(qū)間查找

? ? ? ? 區(qū)間查找的原理跟區(qū)間更新基本一樣，也是看結(jié)點(diǎn)表示的數(shù)據(jù)范圍有不同的操作。同樣，在到某個(gè)結(jié)點(diǎn)的時(shí)候一定要調(diào)用push_down()。不同點(diǎn)在于跟數(shù)據(jù)操作無關(guān)，但是需要一個(gè)sum來儲(chǔ)存收集到的區(qū)間數(shù)據(jù)，同時(shí)最后return。這樣在遞歸完成以后最后返回的就是區(qū)間和了。理解區(qū)間更新后，區(qū)間查找的代碼就非常容易了：

1 // 區(qū)間查找 2 int query_range(int node, int l, int r, int L, int R) 3 { 4 if(l <= L && r >= R) 5 return tree[node]; 6 push_down(node, L, R); 7 int mid = (L+R)/2; 8 int sum = 0; 9 if(mid >= l) 10 sum += query_range(node*2, l, r, L, mid); 11 if(mid < r) 12 sum += query_range(node*2+1, l, r, mid+1, R); 13 14 return sum; 15 }

脫離lazy數(shù)組

? ? ? ? lazy數(shù)組的使用在很大程度將降低了解決問題所耗費(fèi)的時(shí)間，但是也增加了對(duì)模板的修改難度。誠然，lazy很實(shí)用，但是在一些問題的構(gòu)造上并不容易修改。我們平常的區(qū)間修改，整個(gè)區(qū)間的數(shù)值變化是統(tǒng)一的，所以我們能夠在數(shù)學(xué)上提前好多個(gè)結(jié)點(diǎn)先算出來更改情況。但是有很多問題并不是這樣的。

? ? ? ? 例如：hdu4027。11年上海網(wǎng)絡(luò)賽，要求區(qū)間內(nèi)對(duì)每個(gè)節(jié)點(diǎn)的數(shù)值取其二次根。那么再考慮lazy數(shù)組就是徒生煩惱。如果我們拋棄lazy數(shù)組，直接每次都更新到葉子結(jié)點(diǎn)，同時(shí)考慮剪枝，速度也并不慢（500ms）。所以，在區(qū)間操作不平衡，同時(shí)可以剪枝的情況下，完全可以拋棄lazy數(shù)組，從而修改為：

1 boolean cleck(int node,int l,int r){ 2 // 剪枝條件 3 } 4 5 void update_range(int node, int l, int r, int L, int R) { 6 if (L == R) { 7 tree[node] = 1; // 更新方式 8 return; 9 } 10 int mid = (L + R) / 2; 11 if (mid >= l && cleck(node*2,L,mid)) update_range(node * 2, l, r, L, mid); 12 if (mid < r && cleck(node*2+1,mid+1,R)) update_range(node * 2 + 1, l, r, mid + 1, R); 13 tree[node] = tree[node * 2] + tree[node * 2 + 1]; 14 }

拋棄lazy數(shù)組，l與r是區(qū)間范圍，每次遞歸修改的是L與R，表示的是實(shí)際區(qū)間范圍。當(dāng)L == R的時(shí)候就到達(dá)葉子節(jié)點(diǎn)了。每次遞歸的時(shí)候添加剪枝條件，滿足了才能繼續(xù)遞歸。所有非葉子結(jié)點(diǎn)的更新全部在回溯的過程中進(jìn)行。

?

轉(zhuǎn)載于:https://www.cnblogs.com/FengZeng666/p/11445634.html

總結(jié)

以上是生活随笔為你收集整理的线段树原理详解的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。