主席树（静态） 学习笔记

(Updated: )
oi
, ,

在学习主席树之前

你必须学习：

  1. 线段树。
  2. 前缀和。
  3. sort函数、unique函数以及lower_bound函数的使用方法。

什么是主席树

主席树又叫函数式线段树，又名可持久化线段树。所以主席树的名称与他的功能一点关系都没有。 主席树的时空复杂度为$O(n logn)$。

主席树的模板

由于主席树比较难理解，所以结合代码理解一下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
struct node{
    int l,r,sum,cnt;//分别表示左儿子、右儿子、和、子节点中叶子节点个数
}tree[MAXN*20];//主席树与线段树不同，因为主席树中包含着许多线段树，所以内存调大
void insert(int &x,int y,int l,int r,int p){
    x=++ntt;//编号
    tree[x]=tree[y];//先复制上一个节点
    if(l==r){//叶子节点
        tree[x].sum+=p;//和增加
        tree[x].cnt++;//个数增加
        return ;
    }
    int mid=(l+r)>>1;//与线段树差不多
    if(p<=mid) insert(tree[x].l,tree[y].l,l,mid,p);
    else insert(tree[x].r,tree[y].r,mid+1,r,p);
    tree[x].sum=tree[tree[x].l].sum+tree[tree[x].r].sum;//pushup
    tree[x].cnt=tree[tree[x].l].cnt+tree[tree[x].r].cnt;
}
int Sum(int x,int y,int l,int r,int L,int R){//求[l,r]区间中满足值在[L,R]区间的和
    if(L>R) return 0;//没有该区间
    if(L<=l&&r<=R){//符合条件
        return tree[x].sum-tree[y].sum;
    }
    int mid=(l+r)>>1,res=0;//和线段树差不多
    if(L<=mid) res+=Sum(tree[x].l,tree[y].l,l,mid,L,R);
    if(R>mid) res+=Sum(tree[x].r,tree[y].r,mid+1,r,L,R);
    return res;
}
int Cnt(int x,int y,int l,int r,int L,int R){//求[l,r]区间中满足值在[L,R]区间的叶子节点个数
    if(L>R) return 0;//没有该区间
    if(l>r) return 0;//没有该区间
    if(L<=l&&r<=R){//符合条件
        return tree[x].cnt-tree[y].cnt;
    }
    int mid=(l+r)>>1,res=0;//与线段树差不多
    if(L<=mid) res+=Cnt(tree[x].l,tree[y].l,l,mid,L,R);
    if(R>mid) res+=Cnt(tree[x].r,tree[y].r,mid+1,r,L,R);
    return res;
}

首先来看一看模板题： P3834 【模板】可持久化线段树 1（主席树） 这里放一下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<bits/stdc++.h>
#define int long long
#define MAXN 200010 
using namespace std;
int n,m,q,t=0;
int a[MAXN],b[MAXN],rt[MAXN];
struct node{
    int l,r,sum;
}tree[MAXN*20];
void lsh(){
    sort(b+1,b+n+1);
    m=unique(b+1,b+n+1)-(b+1);
    for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+m+1,a[i])-b;
}
void insert(int y,int &x,int l,int r,int p){
    x=++t;
    tree[x]=tree[y];
    tree[x].sum++;
    if(l==r)  return;
    int mid=(l+r)>>1;
    if(p<=mid) insert(tree[y].l,tree[x].l,l,mid,p);
    else insert(tree[y].r,tree[x].r,mid+1,r,p);
}
int query(int x,int y,int l,int r,int k){
    if(l==r) return l;
    int tmp=tree[tree[y].l].sum-tree[tree[x].l].sum;
    int mid=(l+r)>>1;
    if(k<=tmp) return query(tree[x].l,tree[y].l,l,mid,k);
    else return query(tree[x].r,tree[y].r,mid+1,r,k-tmp);
}
signed main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        b[i]=a[i];
    }
    lsh();
    for(int i=1;i<=n;i++) insert(rt[i-1],rt[i],1,m,a[i]);
    for(int l,r,k,i=1;i<=q;i++){
        cin>>l>>r>>k;
        cout<<b[query(rt[l-1],rt[r],1,m,k)]<<endl;
    }
    return 0;
}

例题： SnackDown 2017 Online Elimination Round Prefix XOR 详情见这篇博客