POJ 2104
題意
給定1到n的排列，每次詢問某一區(qū)間內(nèi)的第k小值。
樣例輸入
7 3 1 5 2 6 3 7 4 2 5 3 4 4 1 1 7 3
樣例輸出
5 6 3
主席樹介紹
可持久化線段樹，函數(shù)式線段樹。 有點(diǎn)抽象，能夠理解但還不是很熟練，代碼不長(zhǎng)，但是非常簡(jiǎn)練，有很多技巧，目前當(dāng)做黑箱。
可持久化：每次操作盡量用新節(jié)點(diǎn)表示而不是修改原節(jié)點(diǎn)，這樣就能保留所有歷史信息。 函數(shù)式：函數(shù)式編程里變量常常是不變的，線段樹的函數(shù)式寫法就是這樣。
我們用區(qū)間k小值來解釋。
一些預(yù)處理
離散化（排序+去重），其實(shí)本道題不需要這個(gè)操作。 下面的代碼用到了STL的很多技巧，用unique()函數(shù)去重，用lower_bound()重新映射a數(shù)組。
for (i = 1;i <= n; i++) scanf("%d",&a[i]);for (i = 1;i <= n; i++) b[i] = a[i];sort(b+1,b+n+1);k = unique(b+1,b+n+1) - (b+1);for (i = 1;i <= n; i++) a[i] = lower_bound(b+1,b+k+1,a[i])-b;假設(shè)求整個(gè)區(qū)間的k小值
這個(gè)問題可以用AVL樹做，但是這里介紹一種類似平衡樹的方法。假設(shè)某個(gè)節(jié)點(diǎn)的區(qū)間為[l,r]，則這個(gè)節(jié)點(diǎn)記錄的是在a數(shù)組中有多少個(gè)a[i]滿足l<=a[i]<=r。這樣搜索第k小值時(shí)，如果左孩子數(shù)量小于k則k小值在左子樹中，反之則在右子樹中。復(fù)雜度log(n)。
對(duì)于任意區(qū)間[L,R]
建立n棵線段樹，每棵維護(hù)[1,i]的數(shù)字出現(xiàn)情況。 顯然這n棵線段樹每個(gè)節(jié)點(diǎn)代表的區(qū)間都是一樣的，所以這n棵線段樹同構(gòu)。 用第R棵線段樹去“減”第(L-1)棵線段樹，得出來的結(jié)果就是區(qū)間[L,R]的情況，對(duì)這棵樹套用一遍上面求整個(gè)區(qū)間的方法就可以求出[L,R]中的k小值。
如何節(jié)約空間
上面的方法看起來還是比較具體的，但是會(huì)MLE(n棵線段樹)。 下面的優(yōu)化就是主席樹的精髓：如何扔掉重復(fù)的節(jié)點(diǎn)。有點(diǎn)抽象，這段話看懂了就比較輕松了。
我們發(fā)現(xiàn)，第i棵線段樹和第i+1棵線段樹的區(qū)別在于加入了a[i+1]這個(gè)數(shù)，而a[i+1]在第i棵樹上從根出發(fā)向下走，走過的節(jié)點(diǎn)+1就變成了第i+1棵線段樹。（你可以自己畫一下看看有什么不同）
也就是說相鄰兩棵線段樹之間不同節(jié)點(diǎn)個(gè)數(shù)至多為log(n)個(gè)，換句話說剩下這么多的節(jié)點(diǎn)都是一樣的！ 那么重復(fù)的節(jié)點(diǎn)就可以扔掉了。比如說一個(gè)節(jié)點(diǎn)的左孩子是重復(fù)的，那么我不需要多開一個(gè)節(jié)點(diǎn)，而是直接連到前一棵樹上。 看起來比較復(fù)雜，但是編程中有很多技巧，最后代碼比普通線段樹還短。 P.S. 怕以后忘記這里寫的會(huì)很詳細(xì)。
sol
預(yù)處理這里就不再寫了。
建樹
現(xiàn)在連建樹都要重新寫了TAT。 其實(shí)只要建一棵空樹即可，后面的樹都是連到這棵樹上。 但是后面再update和query的時(shí)候有一個(gè)問題：左孩子和右孩子并不能簡(jiǎn)單的乘2和乘2加1，如何解決？
//root[i]表示第i棵樹的根的位置void build(int l,int r,int &rt){ rt = ++tot; sum[rt] = 0; if (l == r) return; int m = (l + r) >> 1; build(l,m,ls[rt]); build(m+1,r,rs[rt]);}...tot = 0;build(1,k,root[0]);用最樸素的方法：一個(gè)一個(gè)累加！ 這里有一個(gè)技巧就是用了&，也就是說等到搜到這個(gè)點(diǎn)的時(shí)候自然會(huì)把這個(gè)點(diǎn)的位置給傳回來。這個(gè)技巧剩下了不少代碼，在后面的update和query中可以自己體會(huì)。
更新
//ls表示左孩子位置 rs表示右孩子位置 last表示前一棵樹、當(dāng)前節(jié)點(diǎn)的位置void update(int l,int r,int &rt,int last,int p){ rt = ++tot; ls[rt] = ls[last]; rs[rt] = rs[last];//暫時(shí)兩個(gè)孩子都連到前一棵樹的對(duì)應(yīng)孩子上 sum[rt] = sum[last] + 1;//這一步可以解釋是哪log(n)個(gè)點(diǎn)的值發(fā)生了修改！ if (l == r) return; int m = (l + r) >> 1; if (p <= m) update(l,m,ls[rt],ls[last],p); else update(m+1,r,rs[rt],rs[last],p);//修改的那個(gè)節(jié)點(diǎn)開辟出一個(gè)新節(jié)點(diǎn) ls/rs會(huì)回傳新的節(jié)點(diǎn)的位置！前面講到過}...for (i = 1;i <= n; i++) update(1,k,root[i],root[i-1],a[i]);這樣一來就把這“n棵線段樹”都建好了?？梢钥闯鲭m然節(jié)點(diǎn)總數(shù)為nlog(n)，但是卻把所有的情況都記錄下來了，這就是“可持久化”。
查詢
int query(int ss,int tt,int l,int r,int k){ if (l == r) return l; int m = (l + r) >> 1; int cnt = sum[ls[tt]] - sum[ls[ss]];//用第tt棵線段樹減去第ss棵線段樹 if (k <= cnt) return query(ls[ss],ls[tt],l,m,k); else return query(rs[ss],rs[tt],m+1,r,k-cnt);}...while (q--) { scanf("%d%d%d",&ql,&qr,&qk); int res = query(root[ql-1],root[qr],1,k,qk); 有了前面的鋪墊，查詢就比較簡(jiǎn)單了。完整代碼
#include<cmath>#include<cstdio>#include<vector>#include<cstring>#include<iomanip>#include<stdlib.h>#include<iostream>#include<algorithm>#define ll long long#define inf 1000000000#define mod 1000000007#define N 100000using namespace std;int a[N],b[N],root[N*20],ls[N*20],rs[N*20],sum[N*20];int n,q,i,tot,k,ql,qr,qk;void build(int l,int r,int &rt){ rt = ++tot; sum[rt] = 0; if (l == r) return; int m = (l + r) >> 1; build(l,m,ls[rt]); build(m+1,r,rs[rt]);}void update(int l,int r,int &rt,int last,int p){ rt = ++tot; ls[rt] = ls[last]; rs[rt] = rs[last]; sum[rt] = sum[last] + 1; if (l == r) return; int m = (l + r) >> 1; if (p <= m) update(l,m,ls[rt],ls[last],p); else update(m+1,r,rs[rt],rs[last],p);}int query(int ss,int tt,int l,int r,int k){ if (l == r) return l; int m = (l + r) >> 1; int cnt = sum[ls[tt]] - sum[ls[ss]]; if (k <= cnt) return query(ls[ss],ls[tt],l,m,k); else return query(rs[ss],rs[tt],m+1,r,k-cnt);}int main(){ cin>>n>>q; for (i = 1;i <= n; i++) scanf("%d",&a[i]); for (i = 1;i <= n; i++) b[i] = a[i]; sort(b+1,b+n+1); k = unique(b+1,b+n+1) - (b+1); for (i = 1;i <= n; i++) a[i] = lower_bound(b+1,b+k+1,a[i])-b; tot = 0; build(1,k,root[0]); for (i = 1;i <= n; i++) update(1,k,root[i],root[i-1],a[i]); while (q--) { scanf("%d%d%d",&ql,&qr,&qk); int res = query(root[ql-1],root[qr],1,k,qk); printf("%d/n",b[res]); } return 0;}
