摘要

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

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

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

emm就是沒有樹套樹？？？

為什么寫今天這篇文章呢，因為打了一道模板題，《二逼平衡樹》。這題標(biāo)簽很簡潔，樹套樹。于是Sshwy大菜雞淦完這道題，一打開題解：

替罪羊樹？vector？zkw？分塊？二分？

正所謂“平衡樹的題怎么能用平衡樹做呢”，由上述例子我們知道了“樹套樹的題怎么能用樹套樹做呢”，我們可以把這句話概括為套非套?？取：冒?，鑒于這個字有太深厚的底蘊我們還是改成桃非桃吧。

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

1 [LG3380]二逼平衡樹

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

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

1.1 查詢排名

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

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

1.2 查詢第k小值

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

1.3 查詢前驅(qū)后綴

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

1.4 單點修改

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

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

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

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

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

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

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

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

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

這其實是普通平衡樹的弱化版。

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

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

3.1 Vector

至于為什么會有這樣的平非平算法

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

3.2 分塊

3.3 權(quán)值線段樹

3.4 01TRIE

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

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

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

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

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

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

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

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

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

4.1.1 Vector

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

看上去不錯。

4.1.2 分塊

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

4.1.4 平衡樹

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

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

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

4.2.1 Vector

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

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

4.2.2 分塊

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

4.2.3 樹狀數(shù)組

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

4.2.4 線段樹-01TRIE

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

4.2.5 平衡樹

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

5 非樹套樹算法

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

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

5.1 Vector

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

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

5.2 分塊

6 序列套數(shù)集

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

6.1 樹狀數(shù)組

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

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

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

6.2 線段樹-01TRIE

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

6.2.1 套Vector

我相信沒人這么寫

好吧我錯了，洛谷上有人用zkw套vector過了

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

7 數(shù)集套序列

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

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

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

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

7.1.1 套Vector

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

8 擴展-懵逼平衡樹

二逼平衡樹的問題是一個非平衡樹問題。因為其涉及的操作并沒有違背序列特征。它的修改操作不會改變結(jié)構(gòu)。那么如果我們將修改操作改成插入刪除操作呢？

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

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

8.1 非嵌套算法

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

8.1.1 Vector

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

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

8.2 嵌套算法

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

8.2.1 平衡樹

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

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

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

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

8.2.2 數(shù)集套序列

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

1. 查詢區(qū)間排名：查詢在log個值域結(jié)點上，標(biāo)記位于[l,r]的標(biāo)記個數(shù)。

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

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

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

但是這個問題并不好做。因為插入一個數(shù)會使得后面的數(shù)下標(biāo)發(fā)生改變。如果修改所有標(biāo)記的話復(fù)雜度將極高。這里我們有兩種方式維護(hù)。

8.2.2.1 套平衡樹

8.3 值域分塊

8.3.1 不帶區(qū)間限制

8.3.2 塊鏈套分塊

9 總結(jié)

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

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

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

3. 01TRIE與線段樹同源。

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

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

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

7. Vector什么都能干。

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

10 后記

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