摘要

作者嚴正聲名：本文比較沙雕。

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

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

emm就是沒有樹套樹？？？

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

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

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

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

1 [LG3380]二逼平衡樹

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

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

1.1 查詢排名

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

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

1.2 查詢第k小值

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

1.3 查詢前驅后綴

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

1.4 單點修改

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

2 結構？

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

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

維護數(shù)集的問題，常用的算法結構有：權值線段樹、平衡樹、分塊、vector、01TRIE。

對你沒有看錯，我們將STL vector列入了常用算法結構。注意這是“維護”結構，因此算法應當是在線的，故我們不考慮整體二分。

3 某科學的非普通平衡樹

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

維護一個序列，支持查詢全局的排名/第k小值/前驅/后繼，支持單點修改。

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

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

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

3.1 Vector

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

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

3.2 分塊

3.3 權值線段樹

3.4 01TRIE

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

4 某科學的區(qū)間信息維護

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

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

這里我們討論的是做為外桃結構的復雜度。如果你不使用桃算法，復雜度是不同的。

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

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

4.1 基于固定結構

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

4.1.1 Vector

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

看上去不錯。

4.1.2 分塊

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

4.1.4 平衡樹

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

4.2 基于動態(tài)結構

內層基于動態(tài)結構，意味著具體問題（查詢第k小值）無法快速構造具體結構求解。對于求第k小值而言，則通過二分轉化為求排名，于是復雜度比求排名多一個log。我們仍然具體分析一下外層結構對復雜度的影響

4.2.1 Vector

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

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

4.2.2 分塊

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

4.2.3 樹狀數(shù)組

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

4.2.4 線段樹-01TRIE

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

4.2.5 平衡樹

不適合做外層結構。

5 非樹套樹算法

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

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

5.1 Vector

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

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

5.2 分塊

6 序列套數(shù)集

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

6.1 樹狀數(shù)組

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

6.1.1 套權值線段樹-01TRIE

權值線段樹是固定結構，滿足貢獻性。查詢排名，k小值都轉化為權值線段樹的二分，維護log個結點一起跳即可。喜聞樂見的算法。

6.2 線段樹-01TRIE

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

6.2.1 套Vector

我相信沒人這么寫

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

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

7 數(shù)集套序列

我們可以反過來套??！外層維護權值，內層維護區(qū)間。對于外層的數(shù)據(jù)結構，維護某個值域下的下標序列，對內層結構，維護對下標序列的查詢修改。

7.1 權值線段樹-01TRIE

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

同樣的，我們只講權值線段樹做法。

7.1.1 套Vector

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

8 擴展-懵逼平衡樹

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

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

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

8.1 非嵌套算法

我們仍然考慮一些非傳統(tǒng)算法。

8.1.1 Vector

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

的時間內解決問題。

8.2 嵌套算法

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

8.2.1 平衡樹

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

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

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

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

8.2.2 數(shù)集套序列

外層結構維護值域，內層結構維護位置。我們知道值域是固定的，因此可以用權值線段樹-01TRIE。那么我們的問題就變成了：

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

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

3. 查詢前驅后繼：在權值線段樹上二分

4. 插入刪除：在權值路徑上的結點增加標記，刪除標記

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

8.2.2.1 套平衡樹

8.3 值域分塊

8.3.1 不帶區(qū)間限制

8.3.2 塊鏈套分塊

9 總結

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

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

2. 線段樹維護多類信息，用途廣，但是是固定結構。

3. 01TRIE與線段樹同源。

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

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

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

7. Vector什么都能干。

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

10 后記

如果大家喜歡這篇文章，希望大家關注我的博客 ，并關注我的博客轉型計劃～