主席樹的個人理解

主席樹，是一個可以以優良性能去做一個可持久化數據的數據結構。雖時間變得較少，但空間的消耗量是在是難以承受其他的東西。

主席樹的一些基礎知識

離散化

因為在題目中，為了讓選手使用主席樹，必定會將數據范圍開的極大，但實際數字個數又相對于范圍來說很小。 這時候我們不可能開一個極大的線段樹（因為本來空間就不夠用，還這么浪費），所以就無可避免的用到了離散化這個小小的技巧。 在C++庫函數中，有一個函數叫做unique()。它的作用是去掉在地址為a到a+n中，相鄰的量是否重復：是，就將其放置到這段地址的最后。 簡單的來說，就是將一個排完序后的數組去重，返回沒有重復內容的最后地址。 用法如下： 無重復元素的最后地址【返回的值】=unique (開始地址，結束地址) 該函數stl和數組均可使用

歷史版本的作用

這么多棵線段樹，我們也不可能建立多個結構體來保存。我們可以把所有線段樹的節點全部放在tree結構體中，設當前有m個節點，每執行一次插入操作，新增了x個節點，則存放在tree中的第(m+1)個節點至第(m+x)個節點（當然也有別的編號方式）。同時，我們需要一個root數組，其中root[i]表示第i棵線段樹的根節點的編號。 這樣我們就構建完了，來想想——為什么需要歷史版本？回到我們一開始的問題，求區間第k大，假設當前詢問為求[x,y]的第k大，則我們所需要用到的線段樹為第x+1棵到第y棵。從根節點開始，我們將第y棵樹和第x+1棵樹一一對應的節點所維護的值進行相減，其所得到的數就是在所詢問的[x,y]中，當前節點表示的子區間的那幾個數值在整個區間中出現的次數，用t表示，即t=root[y].[1,mid]-root[x-1].[1,mid]。先判斷t是否大于k，如果t大于k，那么說明在區間[x,y]內存在[1,mid]的數的個數大于k，也就是第k大的值在[1,mid]中，否則在[mid+1,r]中。

縮小空間

其實必要的知識已經講得差不多了，但是我們最后還要面臨一個問題——加入一個數，就新建一棵線段樹。我們假設有100000個數吧，且有100000次詢問，試想這一大片龐大的線段樹森林是要占用多大的內存？一定會MLE的（當然數據小就無所謂）。 我們有什么辦法縮小空間需求？我們注意到，每次我們加入一個被離散化后的數x，則從根結點開始向下更新，我們真正相對于前面一棵線段樹的差異之處是很少的！設有一顆[1,4]的線段樹，若當前插入值為3，則[1,4]的左兒子[1,2]沒有絲毫改動！如果又新建一個，完全是浪費。這樣子，我們就有一個方法縮小冗余的空間了——將沒有區別的部分直接指回去！

主席樹的一些操作

單點更新

我們要修改一個葉子結點的值，并且不能影響舊版本的結構。 在從根結點遞歸向下尋找目標結點時，將路徑上經過的結點都復制一份。 找到目標結點后，我們新建一個新的葉子結點，使它的值為修改后的版本，并將它的地址返回。 對于一個非葉子結點，它至多只有一個子結點會被修改，那么我們對將要被修改的子結點調用修改函數，那么就得到了它修改后的兒子。 在每一步都向上返回當前結點的地址，使父結點能夠接收到修改后的子結點。 在這個過程中，只有對新建的結點的操作，沒有對舊版本的數據進行修改。

區間查詢

從要查詢的版本的根節點開始，像查詢普通的線段樹那樣查詢即可。

查詢[1,n]中的第K小值

我們先對數據進行離散化，然后按值域建立線段樹，線段樹中維護某個值域中的元素個數。 在線段樹的每個結點上用cnt記錄這一個值域中的元素個數。 那么要尋找第K小值，從根結點開始處理，若左兒子中表示的元素個數大于等于K，那么我們遞歸的處理左兒子，尋找左兒子中第K小的數； 若左兒子中的元素個數小于K，那么第K小的數在右兒子中，我們尋找右兒子中第K-(左兒子中的元素數)小的數。

查詢區間[L,R]中的第K小值

我們按照從1到n的順序依次將數據插入可持久化的線段樹中，將會得到n+1個版本的線段樹（包括初始化的版本），將其編號為0~n。 可以發現所有版本的線段樹都擁有相同的結構，它們同一個位置上的結點的含義都相同。 考慮第i個版本的線段樹的結點P，P中儲存的值表示[1,i]這個區間中，P結點的值域中所含的元素個數； 假設我們知道了[1,R]區間中P結點的值域中所含的元素個數，也知道[1,L-1]區間中P結點的值域中所包含的元素個數，顯然用第一個個數減去第二個個數，就可以得到[L,R]區間中的元素個數。 因此我們對于一個查詢[L,R]，同步考慮兩個根root[L-1]與root[R]，用它們同一個位置的結點的差值就表示了區間[L,R]中的元素個數，利用這個性質，從兩個根節點，向左右兒子中遞歸的查找第K小數即可。