前言：
最近心(po)血(yu)來(ya)潮(li)學習了一下主席樹。（再不學就落伍了）
主席樹，即可持久化線段樹，支持維護和查詢區間的第\(k\)大（小）、區間不同種類個數等，基于線段樹的思想之上

結構分析

主席樹會維護\([1,n]\)中點的個數（可以理解為，一顆彈珠從樹根放下，滑到葉節點時，走過的路徑都\(+1\)）
現在假設有一組數 \(\{a_1,a_2,...,a_7\}\)，離散化后編號為 \(\{1,2,...,7\}\)，現在以\(\{1,7,6,2,3,5,4\}\)的順序進入主席樹
下面來演示一下這個過程（PowerPoint冠名）








下面來張動圖（PowerPoint冠名）

耐心等一會，總會等到GIF開頭的（該動圖時長32秒）

那么通過這種結構該如何尋找區間第\(k\)大（小）值呢？

---

算法實現

還是原來的數組 \(\{1,7,6,2,3,5,4\}\)，現在來舉個栗子：求\([2,5](\{7,6,2,3\})\)這一段的第\(2\)小值（\(3\)）
首先要了解這樣一個概念：求區間第\(k\)小值，相當于在區間內找一個值，使有\(k\)個數小于等于這個值（廢話）

不(hen)難發現，在主席樹里，左子樹的值一定小于右子樹的值。那么，只要判斷左子樹里的數的個數是否\(\ge2\)，如果是，那么區間第\(2\)小值一定在左子樹里，反之在右子樹里
那么能否建\(N\)棵線段樹呢？　　　 ：小朋友，我來了！
通過認真的觀察，發現——


這兩張圖中，真正修改了值的節點并不多。這時，兩棵線段樹完全可以使用共用的節點，這樣就可以大大的降低空間復雜度。那么，該如何處理\([l,r]\)中比當前值小的數的個數呢？
這里就要用到二分和前綴和的思想了。舉個栗子，如果\([1,l-1]\)中有\(sum_1\)個數比當前值小，\([1,r]\)中有\(sum_2\)個數比當前值小，那么\([l,r]\)中就有 \(sum_2-sum_1\)個值比當前值小
回到剛才的問題：

數組 \(\{1,7,6,2,3,5,4\}\)，求\([2,5](\{7,6,2,3\})\)這一段的第\(2\)小值（\(3\)）

我們挑出第\((2-1)\)次插入時的樹和第\(5\)次插入時的樹，經過觀察——

你發現了什么？
舉個栗子，我們看上一棵樹中的代表\([5,7]\)的節點和下一棵樹的對應節點，可以發現：它們的差就是\(\{7,6,2,3\}\)中在\([5,7]\)上的數的個數。那么，上一棵樹中的代表\([1,4]\)的節點和下一棵樹的對應節點之差為\(2\)，這說明第\(2\)小值必定在\([1,4]\)區間內，由此即可求出第\(2\)小值——\(3\)

---

代碼實現

\(L,R\) 表示左右子樹，\(sum\) 就是圖中所維護的維護\([1,n]\)中點的個數，\(rank\) 為離散化數組，\(root\) 表示這么多線段樹的根。答案遞歸求解即可。( \(fm(x)\) 表示初始化 \(x\) )

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define f(x,y) for(register int i=x;i<=y;i++) #define G ch=getchar() #define rd int #define in(x) x=read(); #define node int #define mid ((l+r)>>1) #define fm(x) memset(x,0,sizeof(x)) #define maxN 200000 using namespace std; inline rd read(); class president_tree {public:node query(int x,int y,int w) {return rank[_query(root[x-1],root[y],1,_size,w)];}void build(int a[],int n){tot=0; fm(rank); fm(root); fm(sum); fm(L); fm(R);for(register int i=1;i<=n;i++) rank[i]=a[i];sort(rank+1,rank+n+1);_size=unique(rank+1,rank+n+1)-rank-1;root[0]=_build(1,_size);for(register int i=1;i<=n;i++)root[i]=update(root[i-1],1,_size,lower_bound(rank+1,rank+_size+1,a[i])-rank);}private:int tot,_size;node rank[maxN+1],root[maxN+1],sum[(maxN<<5)+1],L[(maxN<<5)+1],R[(maxN<<5)+1];;node _build(int l,int r){int k=++tot; sum[k]=0;if(l<r){L[k]=_build(l,mid);R[k]=_build(mid+1,r);}return k;}node update(int pre,int l,int r,int w){int k=++tot; L[k]=L[pre]; R[k]=R[pre]; sum[k]=sum[pre]+1;if(l<r)if(w<=mid) L[k]=update(L[pre],l,mid,w);else R[k]=update(R[pre],mid+1,r,w);return k;}node _query(int u,int v,int l,int r,int k){if(l>=r) return l;int w=sum[L[v]]-sum[L[u]];if(w>=k) return _query(L[u],L[v],l,mid,k);else return _query(R[u],R[v],mid+1,r,k-w);} }; int n,m,a[maxN+1],b[maxN+1],x,y,w; president_tree tree; int main() {in(n); in(m); f(1,n) in(a[i]);tree.build(a,n);f(1,m){in(x); in(y); in(w);printf("%d\n",tree.query(x,y,w));}return 0; } inline rd read() {char ch=getchar();rd num=0,f=1;while((ch<'0' || ch>'9') && ch!='-') G;if(ch=='-') {f=-1; G;}while(ch>='0' && ch<='9') {num=num*10+ch-'0'; G;}return num*f; }

寫在最后

對主席樹的認識與理解，到這篇博客的誕生，是起源于這兩位巨佬的博客的——
最詳細的講解，讓你一次學會主席樹
【Notes】【主席樹】hdu2665 Kth number
在此表示衷心的感謝！
（我才不會告訴你這篇博客寫到一半未保存，網頁就莫名其妙關閉了呢 QWQ）

轉載于:https://www.cnblogs.com/ezsyshx/p/10403244.html

總結

以上是生活随笔為你收集整理的可持久化线段树——主席树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。