主席树(静态) 学习笔记

在学习主席树之前

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

什么是主席树

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

主席树的模板

由于主席树比较难理解,所以结合代码理解一下:
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(主席树) 这里放一下代码:
#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 详情见这篇博客

评论

  1. GREED_VI
    3年前
    2019-2-23 20:53:46

    所以说您还没有理解主席树,只会板子对吗

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇