数据结构2

本篇是一些高级一点的数据结构，好像都是树。。。

线段树合并

其实就是动态开点。这个可以理解一下，帮助理解主席树。
用两种写的形式，一种是函数里传地址，直接修改，另一种是让函数返回新节点的位置。

int update(int &o,int l,int r,int pos,int x){
    if(o==0) o=++idx;
    if(l==r){
        tr[o]+=x;
        col[o]=pos;
        return o;
    }
    int mid=l+r>>1;
    if(pos<=mid) update(ls[o],l,mid,pos,x);
    else update(rs[o],mid+1,r,pos,x);
    pushup(o);
    return o;
}
int merge(int &x,int y,int l,int r){//把y合并到x上，返回的的是新树的根
    if(x==0||y==0){
        x+=y;
        return x;
    }
    if(l==r){
        tr[x]+=tr[y];
        return x;
    }
    int mid=l+r>>1;
    merge(ls[x],ls[y],l,mid),merge(rs[x],rs[y],mid+1,r);
    pushup(x);
    return x;
}

主席树（可持久化权值线段树）

就是每次更新都单独开一个点，记录更新的版本即线段树的根。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,m,a[N],rt[N],tot;
struct node{
    int val,ls,rs;
}tr[N<<5];
int clone(int o){
    tr[++tot]=tr[o];
    return tot;
}
void build(int &o,int l,int r){
    o=++tot;
    if(l==r){
        tr[o].val=a[l];
        return;
    }
    int mid=l+r>>1;
    build(tr[o].ls,l,mid);
    build(tr[o].rs,mid+1,r);
}
int update(int o,int l,int r,int pos,int x){
    o=clone(o);
    if(l==r){
        tr[o].val=x;
        return o;
    }
    int mid=l+r>>1;
    if(pos<=mid) tr[o].ls=update(tr[o].ls,l,mid,pos,x);
    else tr[o].rs=update(tr[o].rs,mid+1,r,pos,x);
    return o;
}
int query(int o,int l,int r,int pos){
    if(l==r) return tr[o].val;
    int mid=l+r>>1;
    if(pos<=mid) return query(tr[o].ls,l,mid,pos);
    else return query(tr[o].rs,mid+1,r,pos);
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    build(rt[0],1,n);
    int v,op,p,x;
    for(int i=1;i<=m;i++){
        cin>>v>>op>>p;
        if(op==1){
            cin>>x;
            rt[i]=update(rt[v],1,n,p,x);
        }
        else{
            rt[i]=rt[v];
            cout<<query(rt[i],1,n,p)<<'\n';
        }
    }
    return 0;
}