前言

主席树全称可持久化权值线段树，用于解决区间第 [算法] 主席树 / 可持久化线段树 - 图1 小问题。

主席树通过对取值范围进行多次建树并进行可持久化操作，利用其可相减的性质来解决区间第 [算法] 主席树 / 可持久化线段树 - 图2 小问题。

前置芝士：可持久化数组

正文

Ⅰ可持久化数组

首先简单提一下可持续化数组。

可持续化数组需要我们在用线段树维护最新数组的同时用线段树维护其历史版本，也就是维护每一次修改前后的版本。

非常暴力的想法就是每一次改点前把线段树复制一遍然后再改，然而这显然是不行的。

我们考虑每一个相邻版本的线段树其实是有很多相似的节点的，所以我们考虑能不能把这些节点合并起来，也就是每次创建新的副本的时候，只创建必须更改的，而和历史版本完全相同的部分直接引用历史版本。这就是可持久化数组的核心思想。

我这里直接给出P3919 【模板】可持久化线段树 1（可持久化数组）的AC代码。

  1. #include<map>
  2. #include<set>
  3. #include<cmath>
  4. #include<queue>
  5. #include<bitset>
  6. #include<vector>
  7. #include<cstdio>
  8. #include<cstring>
  9. #include<cstdlib>
  10. #include<iostream>
  11. #include<algorithm>
  12. #define rep(i,a,b) for(register int i = (a);i <= (b);++i)
  13. #define per(i,a,b) for(register int i = (a);i >= (b);--i)  
  14. typedef long long ll;
  15. typedef unsigned long long ull;
  16. using std::string;using std::cin;using std::cout;
  18. const int N = 1e6+10;
  19. int n,m,a[N],tot,version,opt,p,x;
  21. struct node{
  22.     int l,r,num;
  23.     node * ls , * rs;
  24. }Tree[20*N],*root[2*N];
  26. inline node * create(){return &Tree[++tot];}
  28. inline void build(node * cur,int L,int R){
  29.     cur->l = L , cur->r = R;
  30.     if(L == R){
  31.         cur->num = a[L];
  32.         return;
  33.     }
  34.     int mid = (L+R)>>1;
  35.     cur->ls = create() , cur->rs = create();
  36.     build(cur->ls,L,mid) , build(cur->rs,mid+1,R);
  37.     return;
  38. }
  40. inline node * upd(node * cur,int L,int R){
  41.     node * now = create();
  42.     now->ls = cur->ls , now->rs = cur->rs , now->l = cur->l , now->r = cur->r;
  43.     int mid = (L+R)>>1;
  44.     if(L == R) now->num = x;
  45.     else if(p <= mid) now->ls = upd(now->ls,L,mid);
  46.     else now->rs = upd(now->rs,mid+1,R);
  47.     return now;
  48. }
  50. inline int query(node * cur){
  51.     int mid = (cur->l + cur->r) >> 1;
  52.     if(cur->l == cur->r) return cur->num; 
  53.     else if(p <= mid) return query(cur->ls);
  54.     else return query(cur->rs); 
  55. }
  57. int main(){
  58.     std::ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  59.     //freopen("in.in", "r", stdin);
  60.     cin >> n >> m;
  61.     rep(i,1,n) cin >> a[i];
  62.     root[0] = create();
  63.     build(root[0],1,n);
  64.     rep(i,1,m){ 
  65.         cin >> version >> opt >> p;
  66.         if(opt&1){ // 改点
  67.             cin >> x;
  68.             root[i] = upd(root[version],1,n);
  69.         } else { // 查询
  70.             cout << query(root[version]) << "\n";
  71.             root[i] = root[version];
  72.         }
  74.     }
  75.     return 0;
  76. }

其中特别注意的就是upd()这个函数

  1. inline node * upd(node * cur,int L,int R){
  2.     node * now = create();
  3.     now->ls = cur->ls , now->rs = cur->rs , now->l = cur->l , now->r = cur->r;
  4.     int mid = (L+R)>>1;
  5.     if(L == R) now->num = x;
  6.     else if(p <= mid) now->ls = upd(now->ls,L,mid);
  7.     else now->rs = upd(now->rs,mid+1,R);
  8.     return now;
  9. }

因为除了这个函数，其他部分基本上就是裸的线段树。

我们更新节点的时候，先人为将旧版本的节点完全复制，然后根据改点的需求来更新其中一个自节点，将这个子节点更新。

[算法] 主席树 / 可持久化线段树 - 图3

说明①：右儿子先复制为历史版本的右儿子，然后更新为新的节点，递归当前过程

说明②：左儿子先复制为历史版本的左儿子，然后不再处理左儿子以及左儿子的子树

总之，可持久化数组就是不断动态开点，并最终引回历史版本。而每个版本有各自的root[version]索引。

Ⅱ主席树求静态区间第k小

➀建树

我们先给出主席树的建树流程再进一步做解释。

  • 1.将原数组[算法] 主席树 / 可持久化线段树 - 图4进行去重排序离散化，求得原数组中的元素种类数[算法] 主席树 / 可持久化线段树 - 图5，去重有序数组[算法] 主席树 / 可持久化线段树 - 图6，离散化映射函数[算法] 主席树 / 可持久化线段树 - 图7使[算法] 主席树 / 可持久化线段树 - 图8，记忆化[算法] 主席树 / 可持久化线段树 - 图9的离散化映射数组[算法] 主席树 / 可持久化线段树 - 图10，有[算法] 主席树 / 可持久化线段树 - 图11。
  1. rep(i,1,n) cin >> a[i]; // 读入
  2. rep(i,1,n) b[i] = a[i]; // 复制
  3. b[0] = std::unique(b+1,b+n+1) - b - 1; // 去重
  4. std::sort(b+1,b+b[0]+1,cmp); // 排序
  5. rep(i,1,b[0]) mp[ b[i] ] = i; // 建立映射关系
  6. rep(i,1,n) p[i] = mp[ a[i] ]; // 记忆化
  • 2.建立以root[0]为根，下标范围为[算法] 主席树 / 可持久化线段树 - 图12的最初版本线段树，并将所有节点的权值初始化为[算法] 主席树 / 可持久化线段树 - 图13。
    • 这里给出线段树维护内容：
    • root[i]索引的线段树中，区间为[算法] 主席树 / 可持久化线段树 - 图14的节点维护的是符合[算法] 主席树 / 可持久化线段树 - 图15且[算法] 主席树 / 可持久化线段树 - 图16的元素个数
    • 懒得画图，如果觉得过于抽象请参考这篇
  1. build(root[0],1,b[0]);
  1. inline void build(node * cur,int l,int r){
  2.     cur->l = l , cur->r = r , cur->sum = 0;
  3.     if(l >= r) return;
  4.     int mid = (l+r)>>1;
  5.     cur->ls = create() , cur->rs = create();
  6.     build(cur->ls,l,mid) , build(cur->rs,mid+1,r);
  7.     return;
  8. }
  • 3.枚举[算法] 主席树 / 可持久化线段树 - 图17，创建新的版本使下标为[算法] 主席树 / 可持久化线段树 - 图18的节点值加一，其父节点依然。
  1. rep(i,1,n) root[i] = add(root[i-1],p[i]);
  1. inline node * add(node * cur,int x){
  2.     node * now = create(); // 先复制历史版本
  3.     now->ls = cur->ls , now->l = cur->l , 
  4.     now->rs = cur->rs , now->r = cur->r , 
  5.     now->sum = cur->sum + 1; // 直接从上往下更新，等效于pushup
  6.     if(now->l == now->r) return now; // 看情况更新
  7.     if(now->l <= x && x <= now->ls->r) now->ls = add(cur->ls,x);
  8.     if(now->rs->l <= x && x <= now->r) now->rs = add(cur->rs,x);
  9.     return now;
  10. }
  • 4.建树完毕

我们借助了可持久化数组的历史版本这个特性，用它来维护[算法] 主席树 / 可持久化线段树 - 图19的所有前缀中各个元素的个数。

从主席树的角度来讲，我们需要维护[算法] 主席树 / 可持久化线段树 - 图20的所有前缀串中各元素的个数，为了缩小空间，需要将类似的部分合并，于是利用了可持久化数组的思想。

➁查询

我们先考虑任意[算法] 主席树 / 可持久化线段树 - 图21区间内的第[算法] 主席树 / 可持久化线段树 - 图22小如何借助我们刚刚建的树完成。很显然，我们可以通过二分实现。

我们现在给出一个节点cur，它维护的信息是这样的：

  • 所处版本：[算法] 主席树 / 可持久化线段树 - 图23 （即维护的是[算法] 主席树 / 可持久化线段树 - 图24内[算法] 主席树 / 可持久化线段树 - 图25的各个元素个数）
  • 维护区间：[cur->l,cur->r]
  • 节点权值：cur->sum （表示版本下属于维护区间的元素个数）
  • 左儿子：cur->ls
  • 右儿子：cur->rs

它左儿子和右儿子的维护信息高度相似。

我们现在要找这第[算法] 主席树 / 可持久化线段树 - 图26小，并且我们又知道这个节点左儿子的权值[算法] 主席树 / 可持久化线段树 - 图27，很容易得到以下结论：

  • [算法] 主席树 / 可持久化线段树 - 图28 时，第[算法] 主席树 / 可持久化线段树 - 图29小存在于左儿子维护的区间中
  • [算法] 主席树 / 可持久化线段树 - 图30时，第[算法] 主席树 / 可持久化线段树 - 图31小存在于右儿子维护的区间中

考虑到[算法] 主席树 / 可持久化线段树 - 图32，由于区间不再是前缀，所以我们维护的信息不能直接使用，也就是[算法] 主席树 / 可持久化线段树 - 图33不再能直接得到。想到我们之前维护的是前缀串，联想前缀和思想，我们可以猜测[算法] 主席树 / 可持久化线段树 - 图34这一步这里能否做减法实现，也就是用版本[算法] 主席树 / 可持久化线段树 - 图35和版本[算法] 主席树 / 可持久化线段树 - 图36中维护同一个区间的节点的权值做差，得到的就是[算法] 主席树 / 可持久化线段树 - 图37中属于当前维护范围的元素个数。

类比[算法] 主席树 / 可持久化线段树 - 图38的过程，通过二分递归实现查询。

  1. //query(root[L-1],root[R],k)返回原数组[L,R]中第k小的离散结果，记得反映射回去
  2. inline int query(node * u,node * v,int k){
  3.     if(v->l >= v->r) return v->l;
  4.     int diff = v->ls->sum - u->ls->sum;
  5.     if(k > diff) return query(u->rs,v->rs,k-diff);
  6.     else return query(u->ls,v->ls,k);
  7. }

相关题目

P3834 【模板】可持久化线段树 2（主席树）

  1. #include<map>
  2. #include<set>
  3. #include<cmath>
  4. #include<queue>
  5. #include<bitset>
  6. #include<vector>
  7. #include<cstdio>
  8. #include<cstring>
  9. #include<cstdlib>
  10. #include<iostream>
  11. #include<algorithm>
  12. #define rep(i,a,b) for(register int i = (a);i <= (b);++i)
  13. #define per(i,a,b) for(register int i = (a);i >= (b);--i)  
  14. typedef long long ll;
  15. typedef unsigned long long ull;
  16. using std::string;using std::cin;using std::cout;
  18. const int N = 2e5+10;
  19. int n,m,a[2*N],b[2*N],p[2*N],tot,L,R,k;
  20. std::map<int,int> mp;
  22. struct node{
  23.     int l,r,sum;
  24.     node * ls, * rs;
  25. }Tree[32*N],*root[2*N];
  27. inline node * create(){return &Tree[++tot];}
  29. inline bool cmp(int x,int y){return x < y;}
  31. inline void build(node * cur,int l,int r){
  32.     cur->l = l , cur->r = r , cur->sum = 0;
  33.     if(l >= r) return;
  34.     int mid = (l+r)>>1;
  35.     cur->ls = create() , cur->rs = create();
  36.     build(cur->ls,l,mid) , build(cur->rs,mid+1,r);
  37.     return;
  38. }
  40. inline node * add(node * cur,int x){
  41.     node * now = create();
  42.     now->ls = cur->ls , now->l = cur->l , now->rs = cur->rs , now->r = cur->r , now->sum = cur->sum + 1;
  43.     if(now->l == now->r) return now;
  44.     if(now->l <= x && x <= now->ls->r) now->ls = add(cur->ls,x);
  45.     if(now->rs->l <= x && x <= now->r) now->rs = add(cur->rs,x);
  46.     return now;
  47. }
  49. inline int query(node * u,node * v,int k){
  50.     if(v->l >= v->r) return v->l;
  51.     int diff = v->ls->sum - u->ls->sum;
  52.     if(k > diff) return query(u->rs,v->rs,k-diff);
  53.     else return query(u->ls,v->ls,k);
  54. }
  56. int main(){
  57.     std::ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  58.     //freopen("in.in", "r", stdin);
  59.     cin >> n >> m;
  60.     rep(i,1,n) cin >> a[i];
  61.     rep(i,1,n) b[i] = a[i];
  62.     b[0] = std::unique(b+1,b+n+1) - b - 1; // 去重
  63.     std::sort(b+1,b+b[0]+1,cmp);
  64.     rep(i,1,b[0]) mp[ b[i] ] = i; // 建立映射关系
  65.     rep(i,1,n) p[i] = mp[ a[i] ]; // 记忆化
  66.     root[0] = create();
  67.     build(root[0],1,b[0]);
  68.     rep(i,1,n) root[i] = add(root[i-1],p[i]);
  69.     while(m--){
  70.         cin >> L >> R >> k;
  71.         cout << b[query(root[L-1],root[R],k)] << "\n";
  72.     }
  73.     return 0;
  74. }

可持久化并查集

  1. #include<map>
  2. #include<set>
  3. #include<cmath>
  4. #include<queue>
  5. #include<bitset>
  6. #include<vector>
  7. #include<cstdio>
  8. #include<cstring>
  9. #include<cstdlib>
  10. #include<iostream>
  11. #include<algorithm>
  12. #define rep(i,a,b) for(register int i = (a);i <= (b);++i)
  13. #define per(i,a,b) for(register int i = (a);i >= (b);--i)  
  14. typedef long long ll;
  15. typedef unsigned long long ull;
  16. using std::string;using std::cin;using std::cout;
  18. const int N = 1e5+10;
  19. int n,m,a[2*N],opt,tot,FLAG;
  21. struct node{
  22.     int l,r,fa,deep,num;
  23.     node * ls, * rs;
  24. }Tree[32*N],*root[4*N];
  26. inline node * create(){return &Tree[++tot];}
  28. inline void copy(node * u , node * v){
  29.     u->l = v->l , u->r = v->r;
  30.     u->ls = v->ls , u->rs = v->rs;
  31.     u->fa = v->fa , u->num = v->num , u->deep = v->deep;
  32.     return;
  33. }
  35. inline void build(node * cur,int l,int r){
  36.     cur->l = l , cur->r = r;
  37.     if(l == r){
  38.         cur->fa = cur->num = l , cur->deep = 1;
  39.         return;
  40.     }
  41.     int mid = (l+r)>>1;
  42.     cur->ls = create() , cur->rs = create();
  43.     build(cur->ls,l,mid) , build(cur->rs,mid+1,r);
  44.     return;
  45. }
  47. inline node * upd(node * cur,int x,int F){
  48.     node * now = create();
  49.     copy(now,cur);
  50.     if(cur->l == cur->r && cur->l == x){
  51.         now->fa = F;
  52.         return now;
  53.     } else if(cur->l == cur->r && cur->l == F){
  54.         now->deep = now->deep + FLAG;
  55.         return now;
  56.     }
  57.     if(cur->l <= x && x <= cur->ls->r){
  58.         now->ls = upd(cur->ls,x,F);
  59.         if(cur->rs->l <= F && F <= cur->r && FLAG) now->rs = upd(cur->rs,x,F);
  60.     }
  61.     if(cur->rs->l <= x && x <= cur->r){
  62.         now->rs = upd(cur->rs,x,F);
  63.         if(cur->l <= F && F <= cur->ls->r && FLAG) now->ls = upd(cur->ls,x,F);
  64.     }
  65.     return now;
  66. }
  68. inline node * find(node * cur,int x){
  69.     if(cur->l == cur->r) return cur; 
  70.     if(x <= cur->ls->r) return find(cur->ls,x);
  71.     if(x >= cur->rs->l) return find(cur->rs,x);
  72.     return 0;
  73. }
  75. inline node * get_fa(node * cur,int x){
  76.     node * now = find(cur,x);
  77.     if(x == now->fa) return now;
  78.     else return get_fa(cur,now->fa);
  79. }
  81. int main(){
  82.     std::ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  83.     // freopen("in.in","r",stdin);
  84.     // freopen("out.out","w",stdout);
  85.     int x,y,F,D,f;
  86.     cin >> n >> m;
  87.     root[0] = create();
  88.     build(root[0],1,n);
  89.     rep(i,1,m){
  90.         cin >> opt;
  91.         if(opt == 1){
  92.             cin >> x >> y;
  93.             node * px = get_fa(root[i-1],x) ,* py = get_fa(root[i-1],y);
  94.             if(px->fa == py->fa){
  95.                 root[i] = root[i-1];
  96.                 continue;
  97.             }
  98.             if(px->deep > py->deep) F = px->fa , f = py->fa;
  99.             else F = py->fa , f = px->fa;
  100.             FLAG = px->deep == py->deep;
  101.             root[i] = upd(root[i-1],f,F);
  102.         } else if(opt == 2){
  103.             cin >> x;
  104.             root[i] = root[x];
  105.         } else {
  106.             root[i] = root[i-1];
  107.             cin >> x >> y;
  108.             node * px = get_fa(root[i],x) ,* py = get_fa(root[i],y);
  109.             if(px->fa == py->fa) cout << "1\n";
  110.             else cout << "0\n";
  111.         }
  112.     }
  113.     return 0;
  114. }

参考资料