定义：
**可持久化线段树**是一种可持久化数据结构，也被称为主席树。这种数据结构在普通线段树的基础之上支持**查询某个历史版本**，同时时间复杂度与线段树是同级，**空间复杂度相较而言更高**。 与大部分可持久化数据结构类似，**可持久化线段树尽可能多地共用先前某一个版本的结点，从而节省大量的空间与时间**。思路(以求区间第 (k) 小为例)：
主席树在建树上和权值线段树（按权值建的树）类似，利用权值线段树，我们可以求出整个区间的第 (k) 大（小）值。但对于任意区间上的最值查询，就不好处理。主席树之所以能处理该种问题，关键在于其可持久化的结构，把每一个插入的历史状态都保存下来。
首先，先看用权值线段树如何求整体的第 (k) 大。权值线段树中，每个叶子节点存储某个元素出现次数，一条线段的总和表示区间内所有数出现次数的总和。查询过程：从根节点向下走，如果 (k) 小于等于左子树大小，说明第 (k) 大在左子树的区间中，在左子树中继续查找即可；否则，说明第 (k) 大在右子树的区间中，此时将 (k) 减去左子树大小，并在右子树中继续查找。
如果用权值线段树求任意区间第 (k) 大，那么我们需要建立 (n+1) 棵线段树。第 (i) 棵线段树为在第 (i-1) 棵线段树的基础上插入第 (i) 个数的信息所建的。利用前缀和的思想，要求区间 ([l,r]) 内的第 (k) 大，可以用第 (r) 树的信息减去第 (l-1) 棵树的信息。然后，按照权值线段树求整体第 (k) 的查询步骤即可。 虽然这样在时间上可以，时间复杂度认为 (O(nlogn))，但空间上就完全爆炸了。正常一棵线段树开 (4N) 的空间，那么这种做法需要的空间就是 (4N^2)，显然不可行。
但是思考上述的求解过程，可以发现。每插入一个点的信息，更改的只是该点到根节点之间这条链的信息，其它信息保持不变。即相邻的两棵线段树仅有 (logn) 个节点不同,不同的点共有 (nlogn) 个。所以，就没必要浪费多余的空间去存相同的信息。之前的每棵树就可以用一条链来替代，相同部分直接用前一棵树。那么，空间就大大缩小了。
贴张图：
实现：
1.为了节约空间，主席树中点的并不像一般线段树那样，整体结构在开数组的时候就固定了。而是采用动态开点的方法，用变量 (cnt) 来记总的点数（类似于字典树的建立）。并且编号为 (rt) 的点，其左右儿子节点并不一定为 ((rt<<1)) 和 ((rt<<1|1))，因此需要两个新的数组来存各个点的左右孩子编号。
2.在初始，要建立空树。此后，每次插入点，都在前一棵树的基础上更改。
应用：
主要解决区间问题，利用前缀和的思想，经常和时间相关
1.静态区间第 (k) 大（小）数值：
例题：洛谷P3834
给定 (n) 个整数构成的序列，将对于指定的闭区间查询其区间内的第 (k) 小值。
（代码见模板）
【模板】：
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int a[N],b[N],root[N];
int tree[N<<5],lson[N<<5],rson[N<<5],cnt;//空间开到N<<5,否则RE
int build(int l,int r)
{
int t=++cnt;
if(l==r)
{
tree[t]=0;
//lson[t]=0;
//rson[t]=0;
return t;
}
int mid=(l+r)>>1;
lson[t]=build(l,mid);
rson[t]=build(mid+1,r);
tree[t]=tree[lson[t]]+tree[rson[t]];
return t;
}
int update(int l,int r,int p,int rt)
{
int t=++cnt;
if(l==r)
{
tree[t]=tree[rt]+1;
//lson[t]=0;
//rson[t]=0;
return t;
}
int mid=(l+r)>>1;
if(p<=mid)
{
rson[t]=rson[rt];
lson[t]=update(l,mid,p,lson[rt]);
}
else
{
lson[t]=lson[rt];
rson[t]=update(mid+1,r,p,rson[rt]);
}
tree[t]=tree[lson[t]]+tree[rson[t]];
return t;
}
int query(int u,int v,int l,int r,int k)
{
int mid=(l+r)>>1;
int num=tree[lson[v]]-tree[lson[u]];
if(l==r)
return l;
if(k<=num)
return query(lson[u],lson[v],l,mid,k);
else
return query(rson[u],rson[v],mid+1,r,k-num);
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
b[i]=a[i];
}
sort(b+1,b+1+n);
int len=unique(b+1,b+1+n)-b-1;
cnt=0;
root[0]=build(1,len);
for(int i=1;i<=n;i++)
{
int pos=lower_bound(b+1,b+1+len,a[i])-b;
root[i]=update(1,len,pos,root[i-1]);
}
int l,r,k;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&l,&r,&k);
printf("%d
",b[query(root[l-1],root[r],1,len,k)]);
}
return 0;
}
练习：
hdu4417【静态区间计数】
代码
2.统计区间内不同数的个数：
例题：SPOJ - DQUERY
题意：
给定一个数组 (a[n])，请你统计 (L) 到 (R) 中不同数字的个数。
分析：和求区间第 (k) 小不同，本题的主席树并非建立在权值上。而是建立在位置上。关键在于一个 (last[a]) 数组，存数值 (a) 最后一次出现的位置。每当要插入一个数时，如果该位置为该数第一次出现的位置，那么该位置 (+1)；如果不是，先在前一棵树的基础上，上一次出现的位置 (-1)，建立本次对应的树。然后在本次建立的树的基础上，当前位置 (+1)。
#include <bits/stdc++.h>
using namespace std;
const int N=3e4+5;
const int maxn=1e6+5;
int root[N],last[maxn],tree[N*20],lson[N*20],rson[N*20],cnt;
int build(int l,int r)
{
int t=++cnt;
if(l==r)
{
tree[t]=0;
return t;
}
int mid=(l+r)>>1;
lson[t]=build(l,mid);
rson[t]=build(mid+1,r);
tree[t]=tree[lson[t]]+tree[rson[t]];
return t;
}
int update(int l,int r,int p,int val,int rt)
{
int t=++cnt;
if(l==r)
{
tree[t]=tree[rt]+val;
return t;
}
int mid=(l+r)>>1;
if(p<=mid)
{
lson[t]=update(l,mid,p,val,lson[rt]);
rson[t]=rson[rt];
}
else
{
lson[t]=lson[rt];
rson[t]=update(mid+1,r,p,val,rson[rt]);
}
tree[t]=tree[lson[t]]+tree[rson[t]];
return t;
}
int query(int l,int r,int L,int R,int rt)
{
if(L<=l&&r<=R)
return tree[rt];
int mid=(l+r)>>1;
int ans=0;
if(L<=mid)
ans+=query(l,mid,L,R,lson[rt]);
if(R>mid)
ans+=query(mid+1,r,L,R,rson[rt]);
return ans;
}
int main()
{
int n,q,a;
scanf("%d",&n);
cnt=0;
root[0]=build(1,n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a);
if(last[a]==0)
root[i]=update(1,n,i,1,root[i-1]);
else
{//!!!!
root[i]=update(1,n,last[a],-1,root[i-1]);
root[i]=update(1,n,i,1,root[i]);
}
last[a]=i;
}
scanf("%d",&q);
while(q--)
{
int l,r;
scanf("%d%d",&l,&r);//cout<<tree[root[r]]<<endl;
printf("%d
",query(1,n,l,r,root[r]));
}
return 0;
}
练习：
hdu5919 Sequence II
分析：
求区间内不同数的个数还是按照上一题的步骤，但由于要记子序列的个数第一次出现的位置，因此，从后向前插入点就会方便很多，此时 (last[a]) 就表示第一次出现的位置。
代码
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int a[N],last[N],root[N],tree[N*50],lson[N*50],rson[N*50],cnt;
vector<int>an;
int build(int l,int r)
{
int t=++cnt;
if(l==r)
{
tree[t]=0;
return t;
}
int mid=(l+r)>>1;
lson[t]=build(l,mid);
rson[t]=build(mid+1,r);
tree[t]=tree[lson[t]]+tree[rson[t]];
return t;
}
int update(int l,int r,int pos,int val,int rt)
{
int t=++cnt;
if(l==r)
{
tree[t]=tree[rt]+val;
return t;
}
int mid=(l+r)>>1;
if(pos<=mid)
{
lson[t]=update(l,mid,pos,val,lson[rt]);
rson[t]=rson[rt];
}
else
{
lson[t]=lson[rt];
rson[t]=update(mid+1,r,pos,val,rson[rt]);
}
tree[t]=tree[lson[t]]+tree[rson[t]];
return t;
}
int query(int l,int r,int L,int R,int rt)
{
if(L<=l&&r<=R)
return tree[rt];
int mid=(l+r)>>1;
int ans=0;
if(L<=mid)
ans+=query(l,mid,L,R,lson[rt]);
if(R>mid)
ans+=query(mid+1,r,L,R,rson[rt]);
return ans;
}
int query2(int l,int r,int k,int rt)
{
if(l==r)
return l;
int mid=(l+r)>>1;
int num=tree[lson[rt]];
if(k<=num)
return query2(l,mid,k,lson[rt]);
else
return query2(mid+1,r,k-num,rson[rt]);
}
int main()
{
int t,n,m,cot=0;
scanf("%d",&t);
while(t--)
{
memset(last,-1,sizeof(last));
an.clear();
an.push_back(0);
scanf("%d%d",&n,&m);
cnt=0;
root[n+1]=build(1,n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=n;i>=1;i--)
{
if(last[a[i]]==-1)
root[i]=update(1,n,i,1,root[i+1]);
else
{
root[i]=update(1,n,last[a[i]],-1,root[i+1]);
root[i]=update(1,n,i,1,root[i]);
}
last[a[i]]=i;
}
int l,r;
for(int i=1;i<=m;i++)
{
int tl,tr;
scanf("%d%d",&tl,&tr);
l=min((tl+an[i-1])%n+1,(tr+an[i-1])%n+1);
r=max((tl+an[i-1])%n+1,(tr+an[i-1])%n+1);
int k=query(1,n,l,r,root[l]);
int t=query2(1,n,(k+1)/2,root[l]);
an.push_back(t);
}
printf("Case #%d:",++cot);
for(int i=1;i<=m;i++)
printf(" %d",an[i]);
printf("
");
}
return 0;
}
3.树上两点间的查询：
例题：spoj-COT
题意：给定一个包含 (N) 个结点的树. 树节点从 (1) 到 (N) 编号。每个节点有一个整数权值。
(u;v;k) : 询问从节点 (u) 到节点 (v) 的路径上的第 (k) 小的权值。
【主席树+ (LCA)】
分析：
1.插入顺序按 (dfs) 遍历树的顺序进行，每个点在其父亲节点的基础上建树。
2.把路径上的点的信息整合起来放在一起。一开始想过用树链剖分，但会把路径分成很多的片段，不好处理。联系前缀和的思想，有
(num=tree[lson[u]]+tree[lson[v]]-tree[lca(u,v)]-tree[fa[lca(u,v)]])
代码
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const int mak=20;
vector<int>pic[N];
int a[N],id[N],root[N],fa[mak][N],depth[N],tn[N];
int tree[N*20],lson[N*20],rson[N*20],cnt;
int getid(int val,int len)
{
return lower_bound(id+1,id+1+len,val)-id;
}
int build(int l,int r)
{
int t=++cnt;
if(l==r)
{
tree[t]=0;
return t;
}
int mid=(l+r)>>1;
lson[t]=build(l,mid);
rson[t]=build(mid+1,r);
tree[t]=tree[lson[t]]+tree[rson[t]];
return t;
}
int update(int l,int r,int p,int rt)
{
int t=++cnt;
if(l==r)
{
tree[t]=tree[rt]+1;
return t;
}
int mid=(l+r)>>1;
if(p<=mid)
{
lson[t]=update(l,mid,p,lson[rt]);
rson[t]=rson[rt];
}
else
{
lson[t]=lson[rt];
rson[t]=update(mid+1,r,p,rson[rt]);
}
tree[t]=tree[lson[t]]+tree[rson[t]];
return t;
}
int query(int u,int v,int x,int y,int l,int r,int k)
{
if(l==r)
return l;
int mid=(l+r)>>1;
int num=tree[lson[u]]+tree[lson[v]]-tree[lson[x]]-tree[lson[y]];//前缀和
if(k<=num)
return query(lson[u],lson[v],lson[x],lson[y],l,mid,k);
else
return query(rson[u],rson[v],rson[x],rson[y],mid+1,r,k-num);
}
void dfs(int v,int p,int &t,int len,int d)
{
depth[v]=d;
fa[0][v]=p;
int pos=getid(a[v],len);
root[++t]=update(1,len,pos,root[tn[p]]);
tn[v]=t;
for(int i=0;i<pic[v].size();i++)
{
int u=pic[v][i];
if(u!=p)
dfs(u,v,t,len,d+1);
}
}
void init(int n,int len)
{
int cot=0;
tn[0]=0;
dfs(1,0,cot,len,0);
for(int k=0;k+1<mak;k++)
{
for(int i=1;i<=n;i++)
fa[k+1][i]=fa[k][fa[k][i]];
}
}
int lca(int u,int v)
{
if(depth[u]>depth[v])
swap(u,v);
for(int k=0;k<mak;k++)
{
if((depth[v]-depth[u])>>k&1)
v=fa[k][v];
}
if(u==v)
return u;
for(int k=mak-1;k>=0;k--)
{
if(fa[k][u]!=fa[k][v])
{
u=fa[k][u];
v=fa[k][v];
}
}
return fa[0][u];
}
int main()
{
int n,m,u,v,k;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
id[i]=a[i];
}
for(int i=1;i<n;i++)
{
scanf("%d%d",&u,&v);
pic[u].push_back(v);
pic[v].push_back(u);
}
sort(id+1,id+1+n);
int len=unique(id+1,id+1+n)-id-1;
cnt=0;
root[0]=build(1,len);
init(n,len);
while(m--)
{
scanf("%d%d%d",&u,&v,&k);
int par=lca(u,v);
printf("%d
",id[query(root[tn[u]],root[tn[v]],root[tn[par]],root[tn[fa[0][par]]],1,len,k)]);
}
return 0;
}
练习：
BZOJ 1146【带修改】
4.区间修改：
例题：To the moon HDU - 4348
题意：
一个长度为 (n) 的数组，(m) 个共(4) 种操作：
(1) (C;l;r;d)：区间 ([l,r]) 中的数都 (+d)，同时当前的时间戳 (+1);
(2) (Q;l;r)：查询当前时间戳 (t) 区间 ([l,r]) 中所有数的和 ;
(3) (H;l;r;t)：查询时间戳 (t) 区间 ([l,r]) 的和 ;
(4) (B;t)：将当前时间戳置为 (t) ;
所有操作均合法，开始时间为 (0) 。
数据范围：(1leq n,m leq 10^5,|A_{[i]}| leq 10^9, 1leq l leq r leq n,|d| ≤ 10^4)
分析：
一般的线段树在区间修改时会把 (lazy) 标记下放，但此处不行，因为是动态开点，所以其孩子节点还没有开出。因此主席树的区间修改不需要把 (lazy) 标记下放,只需要保留在该节点即可。当我们修改时，新开的链的每个节点的值是根据其孩子节点的值向上合并得到的，但是有可能该节点所表示的区间被修改过，所以还要加上修改的部分。
即,修改时的区间合并：
tree[t]=tree[lson[t]]+tree[rson[t]]+1LL*(r-l+1)*lazy[t];
查询时，同样要考虑 (lazy) 标记，因为 (lazy) 标记没有下放，所以向下递归相应区间时求答案的时候记得加上，即 (ans) 的初值：
ll ans=lazy[rt]*1LL*(min(R,r)-max(l,L)+1);
另外建空树时 (lazy) 数组记得清空。
其它和普通线段树操作基本相同。
(d) 的数据类型开错了，找了一个下午 bug，难受。
模板：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
ll tree[N*40],lazy[N*40],a[N];
int lson[N*40],rson[N*40],root[N],cnt;
int build(int l,int r)
{
int t=++cnt;
lazy[t]=0;
tree[t]=0;
if(l==r)
{
tree[t]=a[l];
return t;
}
int mid=(l+r)>>1;
lson[t]=build(l,mid);
rson[t]=build(mid+1,r);
tree[t]=tree[lson[t]]+tree[rson[t]];
return t;
}
int update(int l,int r,int L,int R,ll val,int rt)
{
int t=++cnt;
//左右孩子先赋值，因为是区间修改
lson[t]=lson[rt],rson[t]=rson[rt],tree[t]=tree[rt],lazy[t]=lazy[rt];
if(L<=l&&r<=R)
{
tree[t]+=1LL*(r-l+1)*val;
lazy[t]+=val;
return t;
}
int mid=(l+r)>>1;
if(L<=mid)
lson[t]=update(l,mid,L,R,val,lson[rt]);
if(R>mid)
rson[t]=update(mid+1,r,L,R,val,rson[rt]);
tree[t]=tree[lson[t]]+tree[rson[t]]+1LL*(r-l+1)*lazy[t];//后面注意加上lazy标记
return t;
}
ll query(int l,int r,int L,int R,int rt)
{
if(L<=l&&r<=R)
return tree[rt];
ll ans=lazy[rt]*1LL*(min(R,r)-max(l,L)+1);//注意
int mid=(l+r)>>1;
if(L<=mid)
ans+=query(l,mid,L,R,lson[rt]);
if(R>mid)
ans+=query(mid+1,r,L,R,rson[rt]);
return ans;
}
int main()
{
int n,m,l,r,t;
ll d;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]);
int ti=0;
cnt=0;
char ss[5];
root[0]=build(1,n);
while(m--)
{
scanf("%s",ss);
if(ss[0]=='C')
{
scanf("%d%d%lld",&l,&r,&d);
ti++;
root[ti]=update(1,n,l,r,d,root[ti-1]);
}
else if(ss[0]=='Q')
{
scanf("%d%d",&l,&r);
printf("%lld
",query(1,n,l,r,root[ti]));
}
else if(ss[0]=='H')
{
scanf("%d%d%d",&l,&r,&t);
printf("%lld
",query(1,n,l,r,root[t]));
}
else if(ss[0]=='B')
scanf("%d",&ti);
}
}
return 0;
}
相关习题：
hdu2665
bzoj2223
poj2104
poj2761
hdu4348
51Nod-1175
zoj2112
SPOJ COT2
SPOJ COT4
HYSBZ 3295
HYSBZ 3932
历年多校主席树题:
Level Up HDU - 5788