摘要

作者嚴(yán)正聲名：本文比較沙雕。

另外，本文并不是“樹(shù)套樹(shù)入門(mén)”的文章，而是一篇議論性文章。議論性文章是指可能內(nèi)容較受爭(zhēng)議。

在我寫(xiě)這文章的時(shí)侯，輸入法：蜀濤數(shù)，樹(shù)桃樹(shù)，樹(shù)套數(shù)……

emm就是沒(méi)有樹(shù)套樹(shù)？？？

為什么寫(xiě)今天這篇文章呢，因?yàn)榇蛄艘坏滥０孱}，《二逼平衡樹(shù)》。這題標(biāo)簽很簡(jiǎn)潔，樹(shù)套樹(shù)。于是Sshwy大菜雞淦完這道題，一打開(kāi)題解：

替罪羊樹(shù)？vector？zkw？分塊？二分？

正所謂“平衡樹(shù)的題怎么能用平衡樹(shù)做呢”，由上述例子我們知道了“樹(shù)套樹(shù)的題怎么能用樹(shù)套樹(shù)做呢”，我們可以把這句話概括為套非套。咳。好吧，鑒于這個(gè)字有太深厚的底蘊(yùn)我們還是改成桃非桃吧。

于是今天我們就這道模板題探究一下樹(shù)桃樹(shù)問(wèn)題的各類(lèi)算法，并對(duì)所用的結(jié)構(gòu)性質(zhì)做一些分析。

1 [LG3380]二逼平衡樹(shù)

維護(hù)一個(gè)序列，支持區(qū)間查詢排名/第k小值/前驅(qū)/后繼，支持單點(diǎn)修改。

如果沒(méi)有“區(qū)間”兩個(gè)字，變成一個(gè)全局維護(hù)的問(wèn)題，它就是一個(gè)普通平衡樹(shù)問(wèn)題。那么加上“區(qū)間”的限制，即要求我們能高效維護(hù)序列區(qū)間的同類(lèi)信息，滿足要求的數(shù)據(jù)結(jié)構(gòu)很多。于是就有了樹(shù)桃樹(shù)的思路。廣義上說(shuō)，這不僅僅是樹(shù)桃樹(shù)的思路，可以說(shuō)是結(jié)構(gòu)桃結(jié)構(gòu)的思路。但在具體討論各個(gè)算法之前，容我先分析一下每個(gè)操作的性質(zhì)。

1.1 查詢排名

查詢一個(gè)數(shù)x的排名，我們可以理解為求區(qū)間[l,r]中處在值域[L,R]的數(shù)的個(gè)數(shù)。

這個(gè)問(wèn)題是一個(gè)貢獻(xiàn)性的問(wèn)題。貢獻(xiàn)性的問(wèn)題可以被分解為若干子問(wèn)題的和與差。注意，是和與差。它同樣是一個(gè)離散的問(wèn)題，假如你將數(shù)據(jù)離散化，那么查詢排名的結(jié)果是不會(huì)變的。

1.2 查詢第k小值

查詢第k小值，是一個(gè)具體的問(wèn)題，這意味著你不能直接把數(shù)據(jù)離散化，不然查詢的結(jié)果也會(huì)被離散化。而對(duì)于這樣的具體問(wèn)題，要么需要構(gòu)造一個(gè)具體的結(jié)構(gòu)去求解；要么就要把問(wèn)題轉(zhuǎn)化為一類(lèi)離散問(wèn)題求解，并犧牲一定的時(shí)間復(fù)雜度。

1.3 查詢前驅(qū)后綴

查詢前驅(qū)后綴也是具體的問(wèn)題。但是它和查詢第k小值的區(qū)別在于，它還是一個(gè)可分解問(wèn)題。盡管我們不能采用貢獻(xiàn)的方式求前驅(qū)后繼，但是我們可以求出若干個(gè)局部的前驅(qū)后繼，然后取最優(yōu)者。也就是說(shuō)，我們可以將原問(wèn)題劃分為若干子問(wèn)題，求得子問(wèn)題的解后將他們合并出原問(wèn)題的解。這個(gè)所謂的合并不單單指加法，還可以指Max,Min等操作。我將這樣的特性稱為可分解。

1.4 單點(diǎn)修改

修改操作與查詢操作不能比較，故不作敘述。

2 結(jié)構(gòu)？

分析問(wèn)題的性質(zhì)。如果沒(méi)有“區(qū)間”二字，那么這是一個(gè)維護(hù)數(shù)集的問(wèn)題。而“區(qū)間”體現(xiàn)的是序列的特征。

維護(hù)序列的問(wèn)題，常用的算法結(jié)構(gòu)有：樹(shù)狀數(shù)組、線段樹(shù)、平衡樹(shù)、分塊、Vector、01TRIE。

維護(hù)數(shù)集的問(wèn)題，常用的算法結(jié)構(gòu)有：權(quán)值線段樹(shù)、平衡樹(shù)、分塊、vector、01TRIE。

對(duì)你沒(méi)有看錯(cuò)，我們將STL vector列入了常用算法結(jié)構(gòu)。注意這是“維護(hù)”結(jié)構(gòu)，因此算法應(yīng)當(dāng)是在線的，故我們不考慮整體二分。

3 某科學(xué)的非普通平衡樹(shù)

我們先討論解決下面問(wèn)題的復(fù)雜度。注意這并不是普通平衡樹(shù)。

維護(hù)一個(gè)序列，支持查詢?nèi)值呐琶?第k小值/前驅(qū)/后繼，支持單點(diǎn)修改。

這其實(shí)是普通平衡樹(shù)的弱化版。

設(shè) A-B-C-D-E-F 分別表示查詢排名/第k小值/前驅(qū)/后繼，單點(diǎn)修改的復(fù)雜度。

當(dāng)然，這道題有妥妥的平衡樹(shù)做法。就不贅述了。接下來(lái)介紹幾個(gè)具有代表性的平非平算法。并且注意，事實(shí)上處理分塊，下面的其他算法都可以解決普通平衡樹(shù)問(wèn)題。

3.1 Vector

至于為什么會(huì)有這樣的平非平算法

好的現(xiàn)在你知道Vector算法的可行性了。

3.2 分塊

3.3 權(quán)值線段樹(shù)

3.4 01TRIE

01TRIE的本質(zhì)就是權(quán)值線段樹(shù)。只不過(guò)01TRIE的二叉樹(shù)更“偏”一些。權(quán)值線段樹(shù)怎么做，01TRIE就怎么做。

4 某科學(xué)的區(qū)間信息維護(hù)

那么現(xiàn)在我們考慮帶有區(qū)間限制的問(wèn)題。

維護(hù)一個(gè)序列支持區(qū)間查詢排名/第k小值/前驅(qū)/后繼，支持單點(diǎn)修改。

這里我們討論的是做為外桃結(jié)構(gòu)的復(fù)雜度。如果你不使用桃算法，復(fù)雜度是不同的。

事實(shí)上，能夠用結(jié)構(gòu)桃結(jié)構(gòu)算法的題目，通常要求這個(gè)問(wèn)題能快速分解為若干個(gè)子問(wèn)題，并快速將子問(wèn)題的結(jié)構(gòu)合并成原問(wèn)題的答案（這里的“快速”通常只常數(shù)級(jí)別的時(shí)間）。接下來(lái)的討論都基于這樣的條件，因此我們不會(huì)考慮分解與合并問(wèn)題答案的復(fù)雜度，而只考慮解決問(wèn)題的復(fù)雜度。

設(shè)A(n),B(n),C(n),D(n),E(n)分別表示內(nèi)層結(jié)構(gòu)對(duì)于規(guī)模為n的全局問(wèn)題，查詢排名/第k小值/前驅(qū)/后繼，單點(diǎn)修改的復(fù)雜度。

4.1 基于固定結(jié)構(gòu)

如果你的內(nèi)層結(jié)構(gòu)是固定的，意味著任意兩個(gè)相同規(guī)模的同種結(jié)構(gòu)是同構(gòu)的。這類(lèi)數(shù)據(jù)結(jié)構(gòu)包括樹(shù)狀數(shù)組、線段樹(shù)、分塊、Vector、01TRIE。固定結(jié)構(gòu)可以作差（如權(quán)值線段樹(shù)作差），這有助于維護(hù)具體信息（比如第k小值）。那么接下來(lái)我們討論一下外層結(jié)構(gòu)的選擇。

4.1.1 Vector

Vector做區(qū)間維護(hù)的話，差分？如果做差分的話修改就是線性的，否則查詢就是線性的。鑒于原問(wèn)題看上去查詢操作較多，我們用差分吧。由于內(nèi)層結(jié)構(gòu)可以作差，意味著我們可以把問(wèn)題分成兩個(gè)問(wèn)題作差。這樣的總復(fù)雜度就是

看上去不錯(cuò)。

4.1.2 分塊

4.1.3 樹(shù)狀數(shù)組-線段樹(shù)-01TRIE

4.1.4 平衡樹(shù)

利用平衡樹(shù)維護(hù)區(qū)間時(shí)，單個(gè)結(jié)點(diǎn)代表元素，但是單個(gè)結(jié)點(diǎn)維護(hù)的信息代表整個(gè)子樹(shù)（區(qū)間）。這時(shí)就涉及到了結(jié)點(diǎn)信息的合并問(wèn)題，那么對(duì)內(nèi)層結(jié)構(gòu)而言也是一個(gè)合并問(wèn)題，這顯然大大增加時(shí)間復(fù)雜度，因此我們很少使用平衡樹(shù)做為維護(hù)序列特征的外層結(jié)構(gòu)。

4.2 基于動(dòng)態(tài)結(jié)構(gòu)

內(nèi)層基于動(dòng)態(tài)結(jié)構(gòu)，意味著具體問(wèn)題（查詢第k小值）無(wú)法快速構(gòu)造具體結(jié)構(gòu)求解。對(duì)于求第k小值而言，則通過(guò)二分轉(zhuǎn)化為求排名，于是復(fù)雜度比求排名多一個(gè)log。我們?nèi)匀痪唧w分析一下外層結(jié)構(gòu)對(duì)復(fù)雜度的影響

4.2.1 Vector

由于內(nèi)層結(jié)構(gòu)變動(dòng)，那么所有具體問(wèn)題（查詢第k小值、前驅(qū)后繼）都找不到具體結(jié)構(gòu)。查詢第k小值采用了二分的方式轉(zhuǎn)化為離散問(wèn)題，而查詢前驅(qū)后繼是不能用差分做的，因此也要轉(zhuǎn)化為離散問(wèn)題——即利用查詢排名和k小值操作來(lái)求前驅(qū)后繼。這時(shí)的復(fù)雜度就變成了

當(dāng)然，還有一個(gè)方法，你可以選擇Vector不做差分（大霧）

4.2.2 分塊

分塊相比Vector就好很多了。查詢第k小值仍需要二分排名，但查詢前驅(qū)后繼得益于他們的可分解性，可以用分塊查詢塊內(nèi)前驅(qū)后繼，然后合并取最優(yōu)解。因此復(fù)雜度為

4.2.3 樹(shù)狀數(shù)組

這里就體現(xiàn)樹(shù)狀數(shù)組與線段樹(shù)之間的差別了。樹(shù)狀數(shù)組同樣依賴差分，因此要求問(wèn)題具有可貢獻(xiàn)性。此時(shí)它表現(xiàn)得就會(huì)和Vector一樣差。但修改的復(fù)雜度依然好于Vector。

4.2.4 線段樹(shù)-01TRIE

同樣的，得益于查詢前驅(qū)后繼的可分解性，線段樹(shù)、01TRIE可以解決這類(lèi)問(wèn)題

4.2.5 平衡樹(shù)

不適合做外層結(jié)構(gòu)。

5 非樹(shù)套樹(shù)算法

之前我們只討論了數(shù)據(jù)結(jié)構(gòu)在個(gè)體在算法中的局部作用，接下來(lái)我們就考慮原問(wèn)題的算法。

首先介紹兩種桃非桃算法。

5.1 Vector

為了維護(hù)區(qū)間信息，就不維護(hù)有序序列了，直接現(xiàn)場(chǎng)找。需要注意的是，查詢排名是線性的。

查詢第k小可以用快排的思想做到線性復(fù)雜度。方法概括起來(lái)就是一個(gè)二分，但是每次二分后問(wèn)題規(guī)模縮小一半，所以期望復(fù)雜度是線性的。

5.2 分塊

6 序列套數(shù)集

如果你看懂了上文兩個(gè)科學(xué)的章節(jié)以及它們的聯(lián)系，那么接下來(lái)的內(nèi)容就基本可以忽略了。如果沒(méi)有看懂（或者我的敘述有問(wèn)題），那么接下來(lái)我將介紹一些常見(jiàn)的結(jié)構(gòu)桃結(jié)構(gòu)的具體算法做為例子。外層結(jié)構(gòu)用于維護(hù)序列特征（區(qū)間），而內(nèi)層結(jié)構(gòu)維護(hù)數(shù)集信息（值域）。

6.1 樹(shù)狀數(shù)組

這算是很常用的一種做法。筆者使用的就是樹(shù)狀數(shù)組套權(quán)值線段樹(shù)的算法。

6.1.1 套權(quán)值線段樹(shù)-01TRIE

權(quán)值線段樹(shù)是固定結(jié)構(gòu)，滿足貢獻(xiàn)性。查詢排名，k小值都轉(zhuǎn)化為權(quán)值線段樹(shù)的二分，維護(hù)log個(gè)結(jié)點(diǎn)一起跳即可。喜聞樂(lè)見(jiàn)的算法。

6.2 線段樹(shù)-01TRIE

這兩種外層結(jié)構(gòu)可以解決可分解性的問(wèn)題，比樹(shù)狀數(shù)組的適用性更強(qiáng)。套權(quán)值線段樹(shù)-01TRIE是肯定能做的，因此就不講這兩種了，講一種比較偏的。

6.2.1 套Vector

我相信沒(méi)人這么寫(xiě)

好吧我錯(cuò)了，洛谷上有人用zkw套vector過(guò)了

有人問(wèn)，為什么不套平衡樹(shù)？原因很簡(jiǎn)單。前文我們花大量篇幅講內(nèi)層使用變動(dòng)結(jié)構(gòu)的壞處，所以我們自然不會(huì)選擇平衡樹(shù)做為內(nèi)層結(jié)構(gòu)。有興趣的同學(xué)可以下來(lái)自己研究復(fù)雜度。

7 數(shù)集套序列

我們可以反過(guò)來(lái)套?。⊥鈱泳S護(hù)權(quán)值，內(nèi)層維護(hù)區(qū)間。對(duì)于外層的數(shù)據(jù)結(jié)構(gòu)，維護(hù)某個(gè)值域下的下標(biāo)序列，對(duì)內(nèi)層結(jié)構(gòu)，維護(hù)對(duì)下標(biāo)序列的查詢修改。

7.1 權(quán)值線段樹(shù)-01TRIE

外層權(quán)值線段樹(shù)維護(hù)權(quán)值，插入每個(gè)數(shù)時(shí)，在路徑的結(jié)點(diǎn)上記錄他們的下標(biāo)，這樣每個(gè)結(jié)點(diǎn)就有若干下標(biāo)組成序列。于是問(wèn)題轉(zhuǎn)化為標(biāo)記的查詢修改問(wèn)題。

同樣的，我們只講權(quán)值線段樹(shù)做法。

7.1.1 套Vector

7.1.2 套線段樹(shù)-01TRIE-樹(shù)狀數(shù)組

8 擴(kuò)展-懵逼平衡樹(shù)

二逼平衡樹(shù)的問(wèn)題是一個(gè)非平衡樹(shù)問(wèn)題。因?yàn)槠渖婕暗牟僮鞑](méi)有違背序列特征。它的修改操作不會(huì)改變結(jié)構(gòu)。那么如果我們將修改操作改成插入刪除操作呢？

維護(hù)一個(gè)序列，支持區(qū)間查詢排名/第k小值/前驅(qū)/后繼，支持在單點(diǎn)插入/刪除。

插入，是指在兩個(gè)元素之間增加一個(gè)元素。插入刪除是具有數(shù)集特征的操作，而區(qū)間則是具有序列特征的限制，現(xiàn)在要求我們同時(shí)處理這兩個(gè)條件。

8.1 非嵌套算法

我們?nèi)匀豢紤]一些非傳統(tǒng)算法。

8.1.1 Vector

不得不說(shuō)Vector是一個(gè)強(qiáng)有力的算法。利用Vector本身支持的插入刪除操作，利用快排的思想，仍然可以在

的時(shí)間內(nèi)解決問(wèn)題。

8.2 嵌套算法

接下來(lái)考慮桃算法。分析問(wèn)題的特征。原問(wèn)題要求維護(hù)插入刪除的數(shù)集操作，又要維護(hù)區(qū)間查詢的序列操作。

8.2.1 平衡樹(shù)

在前文所述，平衡樹(shù)一直是動(dòng)態(tài)結(jié)構(gòu)而不適合做嵌套結(jié)構(gòu)。在這里，利用在序列中的位置做鍵值，可以方便地維護(hù)一個(gè)動(dòng)態(tài)序列。這里的平衡樹(shù)多指Splay或Treap。

解決了插入刪除操作，接下來(lái)考慮詢問(wèn)。利用平衡樹(shù)的分割合并操作找到區(qū)間對(duì)應(yīng)的子平衡樹(shù)，然后？？？你發(fā)現(xiàn)這個(gè)平衡樹(shù)結(jié)構(gòu)就沒(méi)什么用了。得在結(jié)點(diǎn)上維護(hù)一個(gè)內(nèi)層結(jié)構(gòu)，比如線段樹(shù)-01TRIE之類(lèi)的。而在平衡樹(shù)向上合并信息的時(shí)侯還得寫(xiě)一個(gè)線段樹(shù)合并之類(lèi)的東西。

為什么會(huì)出現(xiàn)這樣的繁瑣算法？因?yàn)槠胶鈽?shù)它只維護(hù)了區(qū)間的特征，它以位置為鍵值，保證了按序列的順序。但是這樣就忽略了數(shù)集的特征，使得你需要在內(nèi)套一個(gè)維護(hù)數(shù)集的結(jié)構(gòu)，也就是線段樹(shù)之類(lèi)的結(jié)構(gòu)以解決問(wèn)題。得益于平衡樹(shù)的特性，你的數(shù)據(jù)結(jié)構(gòu)又需要高效合并，最終使得整個(gè)算法十分可怕。

但是別忘了，我們可以數(shù)集套序列！

8.2.2 數(shù)集套序列

外層結(jié)構(gòu)維護(hù)值域，內(nèi)層結(jié)構(gòu)維護(hù)位置。我們知道值域是固定的，因此可以用權(quán)值線段樹(shù)-01TRIE。那么我們的問(wèn)題就變成了：

1. 查詢區(qū)間排名：查詢?cè)趌og個(gè)值域結(jié)點(diǎn)上，標(biāo)記位于[l,r]的標(biāo)記個(gè)數(shù)。

2. 查詢區(qū)間第k小值：在權(quán)值線段樹(shù)上二分

3. 查詢前驅(qū)后繼：在權(quán)值線段樹(shù)上二分

4. 插入刪除：在權(quán)值路徑上的結(jié)點(diǎn)增加標(biāo)記，刪除標(biāo)記

但是這個(gè)問(wèn)題并不好做。因?yàn)椴迦胍粋€(gè)數(shù)會(huì)使得后面的數(shù)下標(biāo)發(fā)生改變。如果修改所有標(biāo)記的話復(fù)雜度將極高。這里我們有兩種方式維護(hù)。

8.2.2.1 套平衡樹(shù)

8.3 值域分塊

8.3.1 不帶區(qū)間限制

8.3.2 塊鏈套分塊

9 總結(jié)

好的。講到最后，你發(fā)現(xiàn)這個(gè)套是真的很有趣，它能展現(xiàn)出許多結(jié)構(gòu)之間的共性。

1. 樹(shù)狀數(shù)組維護(hù)具有貢獻(xiàn)性的信息，局限性較強(qiáng)，但好寫(xiě)。

2. 線段樹(shù)維護(hù)多類(lèi)信息，用途廣，但是是固定結(jié)構(gòu)。

3. 01TRIE與線段樹(shù)同源。

4. 平衡樹(shù)維護(hù)可以高效合并的信息，并能維護(hù)動(dòng)態(tài)結(jié)構(gòu)問(wèn)題。

5. 分塊能方便地維護(hù)固定線性結(jié)構(gòu)的信息，常數(shù)較小。

6. 塊狀鏈表則比較偏門(mén)，真正用到的地方較少。

7. Vector什么都能干。

利用結(jié)構(gòu)之間的共性，能夠發(fā)現(xiàn)很多算法之間是同源的。希望大家能真正理解這其中的原理。知道了這一點(diǎn)，在下次做數(shù)據(jù)結(jié)構(gòu)題的時(shí)侯可以有一個(gè)更全方位的思路。學(xué)習(xí)算法時(shí)也要多總結(jié)，不要只限于死記硬背。深刻理解他們的通性與差異，可以幫助你選擇合適的結(jié)構(gòu)解題。

10 后記

如果大家喜歡這篇文章，希望大家關(guān)注我的博客 ，并關(guān)注我的博客轉(zhuǎn)型計(jì)劃～