主席树
时间是(查询次数) * logn,空间是(插入次数) * logn

作用1.维护不同版本的线段树,直接版本回退
此时的last,now表示版本信息,值域是坐标 1, n

作用2.支持区间中数与其他数的关系(dfs子树转区间)
此时的last,now表示下标,值域是数值大小通常使用离散化

注意 ： 主席树的空间是插入数的log级别,按照插入数的次数来处理

模板题

无修改的维护区间第k大的数

int t,n,m;
struct code{
    int l,r,cnt;
}tr[N*21];
int rt[N];
int tot;
void pushup(int p){
    tr[p].cnt = tr[tr[p].l].cnt + tr[tr[p].r].cnt;
}
// 插入操作
int insert(int last,int l,int r,int pos){
    int now = ++ tot;
    tr[now] = tr[last];
    if(l == r){
        tr[now].cnt ++;
        return now;
    }
    int mid = l+r>>1;
    if(pos <= mid) tr[now].l = insert(tr[now].l,l,mid,pos);
    else tr[now].r = insert(tr[now].r,mid+1,r,pos);
    pushup(now);
    return now;
}
// 查询区间第k大的数
int query(int last,int now,int l,int r,int k){
    if(l == r) return l;
    int cnt = tr[tr[now].l].cnt - tr[tr[last].l].cnt;
    int mid = l+r>>1;
    if(k<=cnt) return query(tr[last].l,tr[now].l,l,mid,k);
    else return query(tr[last].r,tr[now].r,mid+1,r,k-cnt);
}
void solve(){

    vector<int> v;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        v.push_back(a[i]);
    }
    //离散化值域
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());

    auto find = [&](int x){
        return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
    };
    // 对于每一个点建树
    for(int i=1;i<=n;i++) rt[i] = insert(rt[i-1],1,v.size(),find(a[i]));
    // 区间查询第k大的数
    while(m--){
        int l,r,k; cin>>l>>r>>k;
        cout << v[query(rt[l-1],rt[r],1,v.size(),k)-1] << endl;
    }
    return ;
}

主席树直接在线段树的基础上同时维护不同的版本

就是在某个版本的基础上更新保留了每个版本的信息

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long LL;
const int N = 1000010,mod = 1e9+7 ,P = 19260817;
int t,n,m,A,p,q;
int rnd(){
    A = (7 * A + 13) % P;
    return A;
}
int a[N];

struct code{
    int l,r;
    LL ans;
}tr[N*21];

int tot;
int rt[N];

void pushup(int p){
    tr[p].ans = tr[tr[p].l].ans + tr[tr[p].r].ans;
}

int build(int l,int r){
    int p = ++ tot;
    if(l == r){
        tr[p].ans = a[l];
        return p;
    }
    int mid = l + r >> 1;
    tr[p].l = build(l,mid);
    tr[p].r = build(mid+1,r);
    pushup(p);
    return p;
}

int insert(int last,int l,int r,int pos,int k){
    int now = ++ tot;
    tr[now] = tr[last];
    if(l == r){
        tr[now].ans = k;
        return now;
    }
    int mid = l + r >> 1;
    if(pos <= mid) tr[now].l = insert(tr[now].l,l,mid,pos,k);
    else tr[now].r = insert(tr[now].r,mid+1,r,pos,k);
    pushup(now);
    return now;
}

LL query(int now,int l,int r,int ql,int qr){
    if(ql <= l and r <= qr) return tr[now].ans;
    int mid = l + r >> 1;
    LL res = 0;
    if(ql <= mid) res += query(tr[now].l,l,mid,ql,qr);
    if(qr >  mid) res += query(tr[now].r,mid+1,r,ql,qr);
    return res;
}

void solve(){


    cin >> n >> m >> A >> p >> q;

    for(int i=1;i<=n;i++){
        a[i] = rnd()%q + 1;
        a[i] = 1 << a[i];
    }

    rt[0] = build(1,n);

    for(int i=1;i<=m;i++){
        rt[i] = rt[i-1];
        int op = rnd()%p + 1;
        if(op == 1){
            int l = rnd()%n + 1, r = rnd()%n + 1;
            if(l > r) swap(l,r);
            LL ans = query(rt[i],1,n,l,r);
            cout << __lg(ans) << endl;
        }
        else if(op == 2){
            int l = rnd()%n + 1, r = rnd()%n + 1,k = rnd()%q + 1;
            if(l > r) swap(l,r);
            LL c = query(rt[i],1,n,l,r);
            LL ans = 0;
            for(int j=0;c;j++){
                if(j >= k){
                    if(c&1){
                        ans += (1ll<<j+1) % mod;
                        ans %= mod;
                    }
                    else break;
                }
                c >>= 1;
            }
            cout << ans << endl;
        }
        else if(op == 3){
            int pos = rnd()%n + 1 , k = rnd()% q + 1;
            rt[i] = insert(rt[i],1,n,pos,1<<k);
        }
        else{
            int t = rnd()%i;
            rt[i] = rt[t];
        }
    }
    return ;
}

模板题

树上主席树,利用dfs序来维护,只能查询子树的区间信息

int idx,tot;
int L[N],R[N],rt[N];
struct code{
    int l,r;
    LL cnt;
}tr[21*N];
int insert(int last,int l,int r,int pos,int v){
    int now=++tot;
    tr[now]=tr[last];
    if(l==r){
        tr[now].cnt+=v;
        return now;
    }
    int mid=l+r>>1;
    if(pos<=mid) tr[now].l=insert(tr[now].l,l,mid,pos,v);
    else tr[now].r=insert(tr[now].r,mid+1,r,pos,v);
    tr[now].cnt=tr[tr[now].l].cnt+tr[tr[now].r].cnt;
    return now;
}
LL query(int last,int now,int l,int r,int ql,int qr){
    if(ql <= l and r <= qr) return tr[now].cnt-tr[last].cnt;
    int mid=l+r>>1;
    LL res = 0;
    if(ql <= mid) res += query(tr[last].l,tr[now].l,l,mid,ql,qr);
    if(qr > mid) res += query(tr[last].r,tr[now].r,mid+1,r,ql,qr);
    return res;
}
int w[N],d[N];
vector<int> g[N];
void dfs(int u,int fa){
    L[u] = ++ idx;
    d[u] = d[fa] + 1;
    rt[idx] = insert(rt[idx-1],1,n,d[u],w[u]);
    for(auto&v:g[u]){
        if(v == fa) continue;
        dfs(v,u);
    }
    R[u] = idx;
}
void solve(){

    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>w[i];
    for(int i=1;i<n;i++){
        int a,b; cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }    
    dfs(1,0);
    for(int i=1;i<=n;i++){
        cout << query(rt[L[i]-1],rt[R[i]],1,n,d[i],d[i]+m) << ' ';
    }
    cout << endl;
    return ;
}