主席樹的作用是尋找一個序列的某個區(qū)間的第k大(小)
如:給出一個序列a1,a2...an，有若干個詢問，每個詢問形如(l,r,k)，詢問l到r的第k大是多少
以下內(nèi)容轉(zhuǎn)載自這里
主席樹的每個節(jié)點(diǎn)對應(yīng)一顆線段樹，此處有點(diǎn)抽象。在我們的印象中，每個線段樹的節(jié)點(diǎn)維護(hù)的樹左右子樹下標(biāo)以及當(dāng)前節(jié)點(diǎn)對應(yīng)區(qū)間的信息（信息視具體問題定）。對于一個待處理的序列a[1]、a[2]…a[n]，有n個前綴。每個前綴可以看做一棵線段樹，共有n棵線段樹；若不采用可持久化結(jié)構(gòu)，帶來的嚴(yán)重后果就是會MLE，即對內(nèi)存來說很難承受。根據(jù)可持久化數(shù)據(jù)結(jié)構(gòu)的定義，由于相鄰線段樹即前綴的公共部分很多，可以充分利用，達(dá)到優(yōu)化目的，同時每棵線段樹還是保留所有的葉節(jié)點(diǎn)只是較之前共用了很多共用節(jié)點(diǎn)。主席樹很重要的操作就是如何尋找公用的節(jié)點(diǎn)信息，這些可能可能出現(xiàn)在根節(jié)點(diǎn)也可能出現(xiàn)在葉節(jié)點(diǎn)。
下面是某大牛的理解：所謂主席樹呢，就是對原來的數(shù)列[1..n]的每一個前綴[1..i]（1≤i≤n）建立一棵線段樹，線段樹的每一個節(jié)點(diǎn)存某個前綴[1..i]中屬于區(qū)間[L..R]的數(shù)一共有多少個（比如根節(jié)點(diǎn)是[1..n]，一共i個數(shù)，sum[root] = i；根節(jié)點(diǎn)的左兒子是[1..(L+R)/2]，若不大于(L+R)/2的數(shù)有x個，那么sum[root.left] = x）。若要查找[i..j]中第k大數(shù)時，設(shè)某結(jié)點(diǎn)x，那么x.sum[j] - x.sum[i - 1]就是[i..j]中在結(jié)點(diǎn)x內(nèi)的數(shù)字總數(shù)。而對每一個前綴都建一棵樹，會MLE，觀察到每個[1..i]和[1..i-1]只有一條路是不一樣的，那么其他的結(jié)點(diǎn)只要用回前一棵樹的結(jié)點(diǎn)即可，時空復(fù)雜度為O(nlogn)。
主席樹的節(jié)點(diǎn)存的當(dāng)前節(jié)點(diǎn)的左孩子,右孩子以及當(dāng)前序列位于區(qū)間l,r的個數(shù)。比如,現(xiàn)在是第j顆前綴樹,即現(xiàn)在的序列為a1,a2,a3...aj,假設(shè)現(xiàn)在位于j前綴樹的節(jié)點(diǎn)為rt,rt代表的區(qū)間為l,r,那么rt中存儲的sum值是序列a1,a2...aj位于[ l ,r ]的個數(shù)。
我自己對主席樹的理解，是一個線段樹在修改一個值的時候，它只要修改logn個節(jié)點(diǎn)就可以了，那么我們只要每次增加logn個節(jié)點(diǎn)就可以記錄它原來的狀態(tài)了, 即你在更新一個值的時候僅僅只是更新了一條鏈，其他的節(jié)點(diǎn)都相同，即達(dá)到共用。由于主席樹每棵節(jié)點(diǎn)保存的是一顆線段樹，維護(hù)的區(qū)間相同，結(jié)構(gòu)相同，保存的信息不同，因此具有了加減性。（這是主席樹關(guān)鍵所在，當(dāng)除筆者理解了很久很久，才相通的），所以在求區(qū)間的時候，若要處區(qū)間[l, r]， 只需要處理rt[r] - rt[l-1]就可以了，（rt[l-1]處理的是[1,l-1]的數(shù)，rt[r]處理的是[1,r]的數(shù)，相減即為[l, r]這個區(qū)間里面的數(shù)。
比如說（以區(qū)間第k大為例hdu2665題目戳這里http://acm.hdu.edu.cn/showproblem.php?pid=2665）:
設(shè)n = 4，q= 1;
4個數(shù)分別為4， 1， 3 ，2;
ql = 1, qr = 3, k = 2;
1.建樹
首先需要建立一棵空的線段樹，也是最原始的主席樹，此時主席樹只含一個空節(jié)點(diǎn)，此時設(shè)根節(jié)點(diǎn)為rt[0],表示剛開始的初值狀態(tài)，然后依次對原序列按某種順序更新，即將原序列加入到對應(yīng)位置。此過程與線段樹一樣，時間復(fù)雜度為O（nlogn)，空間復(fù)雜度O（nlog(n))（筆者目前沒有完全搞清究竟是多少， 不過保守情況下，線段樹不會超過4*n）
2.更新
我們知道，更新一個葉節(jié)點(diǎn)只會影響根節(jié)點(diǎn)到該葉節(jié)點(diǎn)的一條路徑，故只需修改該路徑上的信息即可。每個主席樹的節(jié)點(diǎn)即每棵線段樹的結(jié)構(gòu)完全相同，只是對應(yīng)信息（可以理解為線段樹的結(jié)構(gòu)完全一樣，只是對應(yīng)葉子節(jié)點(diǎn)取值不同，從而有些節(jié)點(diǎn)的信息不同，本質(zhì)是節(jié)點(diǎn)不同），此時可以利用歷史狀態(tài)，即利用相鄰的上一棵線段樹的信息。相鄰兩顆線段樹只有當(dāng)前待處理的元素不同，其余位置完全一樣。因此，如果待處理的元素進(jìn)入線段樹的左子樹的話，右子樹是完全一樣的，可以共用，即直接讓當(dāng)前線段樹節(jié)點(diǎn)的右子樹指向相鄰的上一棵線段樹的右子樹；若進(jìn)入右子樹，情況可以類比。此過程容易推出時間復(fù)雜度為O(logn)，空間復(fù)雜度為 O(logn)。如圖：
3.查詢
我們先來看一個簡單的線段樹查詢:
假設(shè)有一個序列a1,a2...an,我們要查詢的是整個序列中第k大。
一個簡單的解法是利用線段樹:
假如線段樹的節(jié)點(diǎn)rt,rt代表的區(qū)間為l,r,線段樹節(jié)點(diǎn)存儲的是值是一個序列位于l,r的個數(shù)。
假設(shè)序列:5 1 2 3 3 2 1 9 8 10,
排序后為 1 1 2 2 3 3 5 8 9 10
第k大為: 1 2 3 4 5 6 7 8 9 10(這里代表k)
1 1 2 2 3 3 5 8 9 10
建好的線段樹如下:
旁邊的數(shù)字為節(jié)點(diǎn)代表的區(qū)間[ l , r ],圈圈的數(shù)字代表序列在[ l , r ]的個數(shù)
那么查詢的代碼如下：
int query(int l,int r,int rt,int k)
{
if(l==r) return l;//or return r
int mid=(l+r)/2;
//如果位于區(qū)間l,r的序列數(shù)>=ｋ,那么在左子樹尋找第k大
if(sum[leftson[rt]]>=k) return query(l,mid,leftson[rt],k);
//否則,在右子樹尋找第k-sum[leftson[rt]]大
else return query(mid+1,r,rightson[rt],k-sum[leftson[rt]]);
}
假設(shè)我現(xiàn)在要找第5大和第8大,那么尋找路徑如下:
其實(shí),主席樹的尋找與此類似,假設(shè)尋找區(qū)間為L,R,那么把第R顆前綴樹和第L顆前綴樹相減得到一顆線段樹,再按照線段樹的查找方法就可以了!
先附上處理好之后的主席樹， 如圖:
是不是看著很暈。。。。。。筆者其實(shí)也暈了，我們把共用的節(jié)點(diǎn)拆開來，看下圖：
啊， 這下清爽多了，一眼看下去就知道每個節(jié)點(diǎn)維護(hù)的是哪棵線段樹了，TAT，如果早就這樣寫估計(jì)很快就明白了，rt[i]表示處理完前i個數(shù)之后所形成的線段樹，即具有了前綴和的性質(zhì)，那么rt[r] - rt[l-1]即表示處理的[l, r]區(qū)間嘍。當(dāng)要查詢區(qū)間[1,3]的時候，我們只要將rt[3] 和 rt[0]節(jié)點(diǎn)相減即可得到。如圖：
這樣我們得到區(qū)間[l, r]的數(shù)要查詢第k大便很容易了，設(shè)左節(jié)點(diǎn)中存的個數(shù)為cnt，當(dāng)k<=cnt時，我們直接查詢左兒子中第k小的數(shù)即可，如果k>cnt，我們只要去查右兒子中第k-cnt小的數(shù)即可，這邊是一道很簡單的線段樹了。就如查找[1, 3]的第2小數(shù)（圖上為了方便，重新給節(jié)點(diǎn)標(biāo)號），從根節(jié)點(diǎn)1向下搜，發(fā)現(xiàn)左兒子2的個數(shù)為1,1<2，所有去右兒子3中搜第2-1級第1小的數(shù)，然后再往下搜，發(fā)現(xiàn)左兒子6便可以了，此時已經(jīng)搜到底端，所以直接返回節(jié)點(diǎn)6維護(hù)的值3即可就可以了。
詢問區(qū)間第k大的模板
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 100010;
int ls[maxn*30], rs[maxn*30], sum[maxn*30];//不知道開多少,開30倍應(yīng)該夠
int T[maxn], tot;
//T[i]為第i顆前綴樹的根節(jié)點(diǎn)所在的位置
//ls[rt]為rt節(jié)點(diǎn)的左孩子所在的位置
//rs[rt]為rt節(jié)點(diǎn)的右孩子所在的位置
//假設(shè)rt是第j顆前綴樹的某個節(jié)點(diǎn),代表的區(qū)間為L-R
//那么sum[rt]表示前j個序列中數(shù)字,位于區(qū)間L-R的數(shù)字的個數(shù)
//build(1, cnt, T[0]);
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]);
}
/*
for(int i = 1; i <= n; i++)
update(T[i-1], a[i], 1, cnt, T[i]);
*/
void update(int last, int p, int l, int r, int& rt)
{//新建一顆前綴樹,last為上一顆前綴樹的節(jié)點(diǎn)的在數(shù)組的位置,rt為新建的前綴樹的節(jié)點(diǎn)在數(shù)組的位置
//p為插入的數(shù)值,l r為插入?yún)^(qū)間
rt = ++tot;//為新前綴樹創(chuàng)建新節(jié)點(diǎn)
//不管三七二十一,新的樹的兩個孩子都接到上一個前綴樹對應(yīng)的兩個孩子那里
//后面那里會有更新的分支,要么更新左孩子,要么更新右孩子,然后ls[rt]或者rs[rt]會新創(chuàng)建一個節(jié)點(diǎn)
ls[rt] = ls[last];
rs[rt] = rs[last];
//因?yàn)樾聵浔壬弦活w前綴樹添加了一個數(shù)字,所以sum[rt]=sum[last]+1
//因?yàn)檫f歸的時候保證了包含p的區(qū)間才有可能出現(xiàn)在這里,sum[rt]=sum[last]+1是準(zhǔn)確的
sum[rt] = sum[last]+1;
//葉子節(jié)點(diǎn)的sum值都已經(jīng)更新了,那肯定要return啦
if(l == r)
return;
int m = l+r>>1;
if(p <= m)
update(ls[last], p, l, m, ls[rt]);//看這里,如果選擇的是左邊,那么ls[rt]會重新創(chuàng)建
else
update(rs[last], p, m+1, r, rs[rt]);//同理,rs[rt]也會重新創(chuàng)建
}
/*
int x, y, k;
printf("%d\n", num[query(T[x-1], T[y], 1, cnt, k)]);
*/
int query(int x, int y, int l, int r, int k)
{
if(l == r)
return l;
int m = l+r>>1;
int cnt = sum[ls[y]]-sum[ls[x]];
if(k <= cnt)
return query(ls[x], ls[y], l, m, k);//左邊第k大
else
return query(rs[x], rs[y], m+1, r, k-cnt);//右邊第k-cnt大
}
int num[maxn], a[maxn], n, q;
void cal()
{
for(int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
num[i] = a[i];
}
tot = 0;
sort(num+1, num+n+1);
// for(int i=1;i<=n;i++)
// printf("%d ",num[i]);
// printf("\n");
int cnt = unique(num+1, num+n+1)-(num+1);//不重復(fù)的數(shù)字個數(shù)
// for(int i=1;i<=cnt;i++)
// printf("%d ",num[i]);
// printf("\n");
build(1, cnt, T[0]);//建一顆空樹
for(int i = 1; i <= n; i++)
{
a[i] = lower_bound(num+1, num+cnt+1, a[i])-num;
//a[i]為離散化后的數(shù)值
// printf("%d ",a[i]);
}
// printf("\n");
for(int i = 1; i <= n; i++)
update(T[i-1], a[i], 1, cnt, T[i]);
while(q--)
{
int x, y, k;
scanf("%d %d %d", &x, &y, &k);
printf("%d\n", num[query(T[x-1], T[y], 1, cnt, k)]);
}
}
int main()
{
while(scanf("%d %d", &n, &q)!=EOF)
cal();
return 0;
}
/*
9 4
1 3 6 1 6 3 11 9 16
*/
這里我再給出在一個序列尋找第k大的代碼,用線段樹實(shí)現(xiàn),可以比較一下與主席樹的不同
#include <cstdio>
#include <cstring>
#include <algorithm>
#define mid ((l+r)>>1)
using namespace std;
const int MAXN = 100010;
int sum[MAXN<<2],num[MAXN],arr[MAXN];
void build(int l,int r,int rt)
{
sum[rt]=0;
if(l==r) return;
build(l,mid,rt<<1);
build(mid+1,r,rt<<1|1);
}
void update(int p,int l,int r,int rt)
{
sum[rt]++;//沿途經(jīng)過的節(jié)點(diǎn)加1
if(l==r) return;
if(p<=mid) update(p,l,mid,rt<<1);
else update(p,mid+1,r,rt<<1|1);
}
//void update(int p,int l,int r,int rt)
//{
// if(l==r)
// {
// sum[rt]++;
// return;
// }
// if(p<=mid) update(p,l,mid,rt<<1);
// else update(p,mid+1,r,rt<<1|1);
// sum[rt]=sum[rt<<1]+sum[rt<<1|1];
//}
int query(int rt,int l,int r,int k)
{
if(l==r) return l;
int cnt=sum[rt<<1];
if(cnt>=k) return query(rt<<1,l,mid,k);//左邊查找第k大
else return query(rt<<1|1,mid+1,r,k-cnt);//右邊查找第k-cnt大
}
int main()
{
int n,m,k,t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
build(1,n,1);
for(int i=1;i<=n;i++)
{
scanf("%d",&arr[i]);
num[i]=arr[i];
}
sort(num+1,num+1+n);
int cnt=unique(num+1,num+1+n)-(num+1);
for(int i=1;i<=n;i++)
{
arr[i]=lower_bound(num+1,num+1+cnt,arr[i])-num;//arr[i]離散化
}
for(int i=1;i<=n;i++)
{
update(arr[i],1,cnt,1);
}
while(m--)
{
scanf("%d",&k);
printf("%d\n",num[query(1,1,cnt,k)]);
}
}
}
K-th Number
題意:
詢問區(qū)間第k大
#include <cstdio>
#include <cstring>
#include <algorithm>
#define mid ((l+r)>>1)
using namespace std;
const int MAXN = 100010*40;
int root[MAXN],ls[MAXN],rs[MAXN],sum[MAXN];
int tot;
void build(int l,int r,int &rt)
{
rt=++tot;
sum[rt]=0;
if(l==r) return;
build(l,mid,ls[rt]);
build(mid+1,r,rs[rt]);
}
void update(int last,int p,int l,int r,int &rt)
{
rt=++tot;
ls[rt]=ls[last];
rs[rt]=rs[last];
sum[rt]=sum[last]+1;
if(l==r) return;
if(p<=mid) update(ls[last],p,l,mid,ls[rt]);
else update(rs[last],p,mid+1,r,rs[rt]);
}
int query(int rtx,int rty,int l,int r,int k)
{
if(l==r) return l;
int cnt=sum[ls[rty]]-sum[ls[rtx]];
if(cnt>=k) return query(ls[rtx],ls[rty],l,mid,k);
else return query(rs[rtx],rs[rty],mid+1,r,k-cnt);
}
int arr[MAXN],num[MAXN];
int main()
{
int n,m,lef,rig,k;
while(scanf("%d%d",&n,&m)!=EOF)
{
tot=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&arr[i]);
num[i]=arr[i];
}
sort(num+1,num+1+n);
int cnt=unique(num+1,num+1+n)-(num+1);
build(1,cnt,root[0]);
for(int i=1;i<=n;i++)
{
arr[i]=lower_bound(num+1,num+1+cnt,arr[i])-num;
}
for(int i=1;i<=n;i++) update(root[i-1],arr[i],1,cnt,root[i]);
while(m--)
{
scanf("%d%d%d",&lef,&rig,&k);
printf("%d\n",num[query(root[lef-1],root[rig],1,cnt,k)]);
}
}
}
