【AgOHの数据结构】主席树

上面是我的入门视频。

又名函数式线段树，可持久化线段树。

可持久化基本都在复制。

每次树的形态发生更改的时候复制节点，一次最多修改 $\log n$ 个节点，空间开 $n\log n$ 。

动态开点，需要记录左右子节点。

一般用来解决刨区间问题或者可持久化问题。

P3919 【模板】可持久化线段树 1（可持久化数组）

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N=1e6+10;

int n,m,a[N],cnt,rt[N];
struct node {int l,r,val;} hjt[N << 5];
int clone(int now) {hjt[++cnt]=hjt[now]; return cnt;}

int build(int now,int l,int r)
{
    now=++cnt;
    if(l == r) {hjt[now].val=a[l]; return now;}
    int mid=(l+r) >> 1;
    hjt[now].l=build(hjt[now].l,l,mid);
    hjt[now].r=build(hjt[now].r,mid+1,r);
    return now;
}

int modify(int now,int l,int r,int pos)
{
    now=clone(now);
    if(l == r) {hjt[now].val=a[pos]; return now;}
    int mid=(l+r) >> 1;
    if(pos <= mid) hjt[now].l=modify(hjt[now].l,l,mid,pos);
    else hjt[now].r=modify(hjt[now].r,mid+1,r,pos);
    return now;
}

int query(int now,int l,int r,int pos)
{
    if(l == r) return hjt[now].val;
    int mid=(l+r) >> 1;
    if(pos <= mid) return query(hjt[now].l,l,mid,pos);
    else return query(hjt[now].r,mid+1,r,pos);
}

int main()
{
//  freopen("work.in","r",stdin); freopen("work.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    rt[0]=build(0,1,n);
    int v,op,p;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&v,&op,&p);
        if(op == 1) {scanf("%d",&a[p]); rt[i]=modify(rt[v],1,n,p);}
        else {printf("%d\n",query(rt[v],1,n,p)); rt[i]=rt[v];}
    }
//  fclose(stdin); fclose(stdout);
    return 0;
}

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

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N=2e5+10;
typedef long long ll;

vector <int> v;
struct node {int l,r,sum;} hjt[N << 5];
int cnt,root[N],a[N],n,m;

inline int getid(int x) {return lower_bound(v.begin(),v.end(),x)-v.begin()+1;}
void ins(int l,int r,int pre,int &now,int p)
{
    hjt[now=++cnt]=hjt[pre];
    hjt[now].sum++;
    if(l == r) return ;
    int mid=(l+r) >> 1;
    if(p <= mid) ins(l,mid,hjt[pre].l,hjt[now].l,p);
    else ins(mid+1,r,hjt[pre].r,hjt[now].r,p);
}
int query(int l,int r,int L,int R,int k)
{
    if(l == r) return l;
    int mid=(l+r) >> 1;
    int tmp=hjt[hjt[R].l].sum-hjt[hjt[L].l].sum;
    if(k <= tmp) return query(l,mid,hjt[L].l,hjt[R].l,k);
    else return query(mid+1,r,hjt[L].r,hjt[R].r,k-tmp);
}

int main()
{
//  freopen("work.in","r",stdin); freopen("work.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) {scanf("%d",&a[i]); v.push_back(a[i]);}
    sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end());
    for(int i=1;i<=n;i++) ins(1,n,root[i-1],root[i],getid(a[i]));
    int l,r,k;
    while(m--)
    {
        scanf("%d%d%d",&l,&r,&k);
        printf("%d\n",v[query(1,n,root[l-1],root[r],k)-1]);
    }
//  fclose(stdin); fclose(stdout);
    return 0;
}

几道写过题解的题

• P6166
• CF840D
• SP3266
• SP23776