权值线段树

模板

无（逃

解释

在线段树里，每个区间存的是对应区间的积/和
而在权值线段树中，我们存的是每个数的桶
什么意思呢？
首先，在讲这之前，要先介绍一下离散化
因为我们输入的数可能会很大，这种情况不利于用桶来存放，而恰好我们只用考虑数之间的相对大小，所以我们把数用他们在数列中的序号代替
看到这里，想必你也明白了，普通的权值线段树是离线的，并不支持在线修改
然后接下来就是正题啦
假设我们现在有一个数组 $[1,2,2,7,7,8]$，我们把它离散化一下，得到了 $[1,2,2,3,3,4]$
这时候，我们就可以得到一个桶的序列 $[1,2,2,1]$，这是基础
接下来我们把它按正常的线段树维护
那接下来怎么查询呢？
我们不妨假设要查第4小，这时候我们发现，第一次比较时，左区间是3，也就是我们要查的数在右边，于是我们偏向右边，接着左区间是2，那我们再偏向左边，于是最后我们到了第3个桶，也就是7所在的桶。就这样，我们查出来了
是不是很神奇呢

持久化线段树

模板

#include<iostream>
#include<cstdio>
#define N 1000005
#define M 1000005
#define rs(x) (st[x].rson)
#define ls(x) (st[x].lson)
#define value(x) (st[x].v)
using namespace std;

typedef struct{
    int v,lson,rson;
} node;
node st[N*30];
// 快读模板 read()
int n,m,ar[N],tot;
void build(int l,int r,int no){
    if(l==r){ st[no]={ar[l],-1,-1};return;}
    int mid=(l+r)>>1;
    ls(no)=++tot,build(l,mid,ls(no));
    rs(no)=++tot,build(mid+1,r,rs(no));
    value(no)=value(ls(no))+value(rs(no));
}
void modify(int l,int r,int ol,int ne,int k,int x){
    if(l==r) value(ne)=x;
    else{
        ls(ne)=ls(ol),rs(ne)=rs(ol);
        int mid=(l+r)>>1;
        if(k<=mid) modify(l,mid,ls(ol),(ls(ne)=++tot),k,x);
        else modify(mid+1,r,rs(ol),(rs(ne)=++tot),k,x);
        value(ne)=value(ls(ne))+value(rs(ne));
    }
}
int query(int l,int r,int no,int k){
    if(l==r) return value(no);
    int mid=(l+r)>>1;
    if(k<=mid) return query(l,mid,ls(no),k);
    else return query(mid+1,r,rs(no),k);
}
int roots[M],rootcnt;
int main(){
    read(n);read(m);
    int t,a,b,c;
    for(int i=1;i<=n;i++) read(ar[i]);
    build(1,n,++tot);
    roots[0]=1,rootcnt=1;
    for(int i=1;i<=m;i++){
        read(a),read(t);
        if(t==1){
            read(b),read(c);
            modify(1,n,roots[a],(roots[rootcnt++]=++tot),b,c);
        }else{
            read(b);
            printf("%d\n",query(1,n,roots[rootcnt++]=roots[a],b));
        }
    }
}

主席树(可持久化权值线段树)

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

#define N 200005
#define ls(x) (st[x].lson)
#define rs(x) (st[x].rson)
#define value(x) (st[x].v)
using namespace std;
int c[N],d[N];

struct{
    int lson,rson,v;
}st [N*50];
// 快读模板 read()
int n,m,dn,tot;
void modify(int l,int r,int ol,int ne,int k){
    if(l==r){
        value(ne)=value(ol)+1;
        return;
    }
    ls(ne)=ls(ol),rs(ne)=rs(ol);
    int mid=(l+r)>>1;

    if(k<=mid) modify(l,mid,ls(ol),ls(ne)=++tot,k);
    else modify(mid+1,r,rs(ol),rs(ne)=++tot,k);
    value(ne)=value(ls(ne))+value(rs(ne));
}
int query(int l,int r,int ol,int ne,int k){
    if(l==r) return d[l];
    int mid=(l+r)>>1;
    if(k<=value(ls(ne))-value(ls(ol))) return query(l,mid,ls(ol),ls(ne),k);
    else return query(mid+1,r,rs(ol),rs(ne),k-value(ls(ne))+value(ls(ol)));
}
int roots[N];
int main(){
    int l,r,k;
    read(n),read(m);
    for(int i=1;i<=n;i++) read(c[i]),d[i]=c[i];
    sort(d+1,d+1+n),dn=unique(d+1,d+1+n)-d-1;
    for(int i=1;i<=n;i++){
        c[i]=lower_bound(d+1,d+dn+1,c[i])-d;
        roots[i]=++tot;
        modify(1,n,roots[i-1],roots[i],c[i]);
    }
    for(int i=1;i<=m;i++){
        read(l),read(r),read(k);
        printf("%d\n",query(1,n,roots[l-1],roots[r],k));
    }
}

可持久化并查集

模板

#include<iostream>
#define N 100005
#define M 200005

#define ls(x) (st[x].lson)
#define rs(x) (st[x].rson)
#define fa(x) (st[x].fa)
#define dep(x) (st[x].dep) 
using namespace std;
struct {
    int lson,rson,fa,dep;
} st[N*40];
int n,m;
int tot,roots[M];

void build(int l,int r,int no){
    if(l==r){
        fa(no)=l,dep(no)=1;
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,ls(no)=++tot);
    build(mid+1,r,rs(no)=++tot);
}

int query(int l,int r,int no,int k){
    if(l==r){
        return fa(no);
    }
    int mid=(l+r)>>1;
    if(k<=mid) return query(l,mid,ls(no),k);
    else return query(mid+1,r,rs(no),k);
}
int find(int x,int root){
    int fa=query(1,n,root,x);
    if(x==fa) return x;
    else return find(fa,root);
}

void merge(int l,int r,int ol,int ne,int k,int fa){
    if(l==r){
        fa(ne)=fa;
        dep(ne)=dep(ol);
        return;
    }
    ls(ne)=ls(ol),rs(ne)=rs(ol);
    int mid=(l+r)>>1;
    if(k<=mid) merge(l,mid,ls(ol),ls(ne)=++tot,k,fa);
    else merge(mid+1,r,rs(ol),rs(ne)=++tot,k,fa);
}

int main(){
    ios::sync_with_stdio(0);cout.tie(0);cin.tie(0);
    cin>>n>>m;
    build(1,n,roots[0]=++tot);
    for(int i=1;i<=m;i++){
        static int opt,a,b;
        cin>>opt;
        if(opt==1){
            cin>>a>>b;
            roots[i]=++tot;
            int fax=find(a,roots[i-1]),fay=find(b,roots[i-1]);
            if(dep(fax)>dep(fay)) swap(fax,fay); 
            merge(1,n,roots[i-1],roots[i],fax,fay);
            if(dep(fax)==dep(fay)){
                dep(fay)++;
            }
        }else if(opt==2){
            cin>>a;
            roots[i]=roots[a];
        }else{
            roots[i]=roots[i-1];
            cin>>a>>b;
            int fax=find(a,roots[i]),fay=find(b,roots[i]);
            cout<<(fax==fay?1:0)<<"\n";
        }
    }
}

一些解释

我们知道，对于那些只关心子节点与父节点关系的题，可以使用并查集。
而我们又知道，并查集用一个 fa[] 数组来存储父亲，而线段树维护的也是一个数组
Ah, apple pen于是我们就想到可以用线段树维护并查集
而我们还知道，线段树可持久化，于是，并查集也可以持久化\