0、目录

主席树

1、主席树

1.1、模板

#define lson(i) (tre[(i)].ls)
#define rson(i) (tre[(i)].rs)
#define sumv(i) (tre[(i)].sum)

///nlogn空间复杂度
struct Tre {
    int ls,rs,sum;
    Tre() {
        ls=rs=sum=0;
    }
} tre[maxn*20];

int rt[maxn],tot;

int _v;
void update(int &o,int l,int r) {
    tre[++tot]=tre[o],o=tot;
    if(l==r) {
        sumv(o)++;
    } else {
        if(_v<=mid) update(lson(o),l,mid);
        else update(rson(o),mid+1,r);
        sumv(o)=sumv(lson(o))+sumv(rson(o));
    }
}

///求区间第k大
int _res;
void query(int o1,int o2,int l,int r,int k) {
    if(l==r) {
        _res=l;
    } else {
        ///前缀和思想
        int cnt=sumv(lson(o2))-sumv(lson(o1));
        if(cnt>=k) query(lson(o1),lson(o2),l,mid,k);
        else query(rson(o1),rson(o2),mid+1,r,k-cnt);
    }
}

///0是个超级节点
void init() {
    rt[0]=tot=0;
}

void solve() {
    for(int i=1; i<=n; i++) {
        _v=arr[i];
        rt[i]=rt[i-1];
        update(rt[i],1,n);
    }
}