前置技能——線段樹

線段樹屬于一種高級數據結構。在學習線段樹的時候需要的知識鋪墊比較多。建議先對樹狀結構、二分以及遞歸編程法有深刻的認識和理解，然后再進行線段樹的學習。
簡單線段樹支持單點查詢，區間查詢，單點修改，區間修改。

權值線段樹

普通線段樹維護的信息是數列的區間信息，比如區間和、區間最大值、區間最小值等等。在維護序列的這些信息的時候，我們更關注的是這些數本身的信息，換句話說，我們要維護區間的最值或和，最關注的是這些數總共的信息。而權值線段樹維護一列數中數的個數。
來看這樣一個數列：
1 1 1 2 3 3 4 5 5 6 6 7
一棵權值線段樹的葉子節點維護的是“有幾個1”，“有幾個2”...，他們的父親節點維護的是“有幾個1和2”。
傳統的線段樹用于維護一條線段上的區間，可以方便地查詢區間信息。而如果將線段樹轉化為『權值線段樹』，每個葉子節點存儲某個元素出現次數，一條線段的總和表示區間內所有數出現次數的總和。
利用權值線段樹可以方便地求出整體第 k 大 —— 從根節點向下走，如果 k 小于等于左子樹大小，說明第 k 大在左子樹的區間中，在左子樹中繼續查找即可；否則，說明第 k 大在右子樹的區間中，此時將 k 減去左子樹大小，并在右子樹中繼續查找。
查找過程類似平衡樹，時間復雜度為O(logn) 。

例題引入

給定N個正整數（\(10^6\) 范圍內），一共M次插入及詢問，每次都要詢問當前序列的第k大的數。
其中 \(M≤2×10^5\)，保證詢問有答案。

問題分析

該問題用平衡樹可以做，但有沒有更簡單的做法呢？
我們考慮類比平衡樹，用線段樹解決。平衡樹為什么可以做？因為他它證了當前節點左兒子比他小，右兒子比他大，并且維護了每個節點的size，所以可以找到k大。那我們想用線段樹該怎么做呢？
這里我們轉換一下思路，用每個葉子節點記錄下當前自然數出現的次數。例如當前某個葉子節點管理的區間是[3,3],那么他記錄的就是3這個自然數當前出現的次數。
\(\color{red}{權值線段樹的節點用來表示一個區間的數出現的次數}\)
例如： 數1和2 分別出現3次和5次，則節點1 記錄3，節點2 記錄5， 1和2的父節點記錄它們的和8 .

權值線段樹和簡單線段樹的區別

權值線段樹維護的是桶，按值域開空間，維護的是個數。
簡單線段樹維護的是信息，按個數可開空間，維護的是特定信息。

參考學習：http://www.rzrgm.cn/young-children/p/11787493.html

主席樹

前面的權值線段樹有什么好的呢？
再觀察觀察，就可以發現一個非常驚人的事情，兩顆權值線段樹可以類似前綴和直接做減法！！比如我們用插入了b以后的權值線段樹減去插入a之前的權值線段樹得到的權值線段樹，得到的權值線段樹就相當于只插入a到b之間的數的權值線段樹！！我們可以用這個性質干什么呢？某些讀者可能已經想到了。區間K大！！！
這種類似前綴和用權值線段樹的東西就叫做可持久化線段樹，也叫主席樹。

參考學習：http://www.rzrgm.cn/LonecharmRiver/articles/9087536.html