主席树 | Believe it

nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial

转移自老blog

主席树

------ 2019.4.30

什么是主席树

        主席树是可持久化权值线段树,支持点修改,区间查询。

静态数组区间第k大

        先来个题，给一个数组，多组询问，每次询问区间第k大(小),

为数组的每一个前缀建立一颗线段树

        但是这样子，空间会爆炸，时间也一样爆炸，但是我们发现前缀 之间是有联系的，两个相邻的前缀之间只有一个权值的差距，所以可以考虑利用以前的节点信息以节省空间和时间。

具体实现

        因为两个相邻的前缀之间只有一个权值的差距，所以两颗线段树树之间 只有一条链的差距。我们尝试让新树的指针指向旧树，然后对新树那条有区别的链重新开辟空间即可。

时空复杂度分析

        因为一条链的差距，导致每次建树，空间至多开辟lgn,同理，时间为lgn

如何解决静态区间第k大

        我们有了每一个前缀的权值线段树，于是我们让两个前缀权值线段树相减，即可得到 任意区间的权值线段树,现在问题化简了，已知某个区间的权值线段树，询问区间第k大，我们在这颗权值线段树上二分答案即可。二分是这样实现的， 如果当前跑到了叶子结点，说明叶子节点权值为答案，否则把k和当前节点左子树的权值和比较，若k小，说明答案在右子树，否则在左子树。

一个优化（可以先不看）

        很多人写主席树，带一个build函数，用来建立一颗第一个版本的树，理解确实好理解， 然而，真的有必要吗？其实是没有的，我们来看看那颗树长啥样？由于没有权值，所以那颗树维护的所有节点的权值都是0，注意：都是0。也就是说 你浪费了2*n的空间，存了一堆0？是的，这里我们来优化一下，我们来看这样一个节点，他的权值为0,他的左儿子指向自己，他的右儿子指向自己， 看看，这是一个包含了一个节点的非简单图，他有自环来着。我们尝试对这一个节点安装访问曾经访问过的节点的方式带着区间端点dfs下去，你会发现一个奇妙的 事情，你得到了和之前花费2*n个节点建立空树一样的效果。于是我们优化了这一个空间复杂度，此优化在此不太明显，O(lg)-O(1)算啥呀。但是 当我们处理后面的动态区间问题时，此优化起到了非常大的作用，这就是图的优势打个广告：此优化像极了后缀自动机

---

动态数组区间第k大

        前面的题目已经解决了,但是当数组变化(点修改)伴随着区间第k大查询的时候，我们该怎么办呢？

重新研究主席树

        主席树，说白了，就是原数组所有前缀的权值线段树+时空优化。查询的时候同个两个 前缀和的差值得到任意区间的权值线段树。我们发现这和一个题目很相似。

区间和查询

        想必不少人都做过这样的一个题目，给你一个固定的数组，给出很多询问，每次询问 一个区间，让你输出区间和。这个题目很简单，我们只需要预处理前缀和，对于任意询问，用两个前缀和向减即可解决，

带修改的区间和查询

        当上一个题目发生变化:数组可能会点修改，点修改伴随着区间和查询，的时候，我们 就不能用前缀和了，这样很困难，于是树状数组出现了。限于重点，此处不解释树状数组

将树状数组的思路用到主席树上(带修主席树)

        我们让主席树换一种建法，不用前缀和，用树状数组的方案，每一颗主席树rt[i]维护 区间(i&(i-1),i]的权值线段树。如此一来，当我们进行点修改的时候，只需要修改lg颗权值线段树，当我们查询的时候，要lg颗线段树才能组成 任意区间的权值线段树。相当于牺牲了一部分查询时间，换取更新操作的加速。

带修主席树？线段树动态开点？

        当主席树方式变了之后，我们惊讶的发现，权值线段树不能简单的继承他的儿子了，他比儿子 多好多新的权值信息要维护，比方说1100(12)，他的儿子是1000(8),他俩差了100(4)个权值,如果我们还是采用之前的继承儿子权值线段树的方式，编码会很复杂 这里提出一种新的方法:超级超级超级大大大暴力建树，每一个树状数组节点（权值线段树）我们都从0开始建树。有兴趣可以去打表试试，看似暴力其实一点都不暴力， 除非你不用上文谈到的的那个"一个优化" 我们最多调用update函数lg*lg次。于是，这个带修主席树，被yyb成为了线段树动态开点。 不知道yyb，你可太骚了，自己百度去

线段树套主席树

        此坑待填。

---

树形主席树

        主席树太强了，我们骚里个骚，把它放到树上去，来个树套树

静态树上路径第k大

        是这样一个问题，给你一棵树，每个节点都有权，很多询问，问你任意两点之间的最短路径上经过的点中 点权第k大是谁

树上差分

        前缀也没谁了，树上一个点前缀就是这个点到根的路径上经过的点的集合，我们安装这种想法建立一个树上的 主席树，儿子是父亲的继承版本中的一个，父亲是儿子的前一个版本，时空复杂度不高，

树上任意路径？

        比方说u->v ，我们假设lca为u和v的lca，假设fa为lca的父亲，那么我们用u的权值线段树加上v的权值线段树减去lca的 权值线段树再减去fa的权值线段树，得到的就是u->v这条路径的权值线段树，ok你已经学完了此博文

可变的树上路径第k大

https://www.luogu.org/problemnew/solution/P4175

// 没有build 因为不需要 空树就是rt[0],是建好了的
const int maxn = 2e5+5;
int ls[maxn*20*2],rs[maxn*20*2],siz[maxn*20*2],tot,rt[maxn];//update用了几次，就要乘以多少

void ini(){tot=0;}

void update(int pre,int&u,int l,int r,int pos,int val){//把u按照pre复制，然后更新pos
    u=++tot;
    ls[u]=ls[pre];rs[u]=rs[pre];
    siz[u]=siz[pre]+val;
    if(l==r)return ;
    int mid=(l+r)>>1;
    if(pos<=mid) update(ls[pre],ls[u],l,mid,pos,val);
    else update(rs[pre],rs[u],mid+1,r,pos,val);
}

int query(int x,int y,int l,int r,int k){//查询（y树-x树）差值的区间第k小
    if(l==r)return l;
    int s=siz[ls[y]]-siz[ls[x]];
    int mid=(l+r)>>1;
    if(k<=s) return query(ls[x],ls[y],l,mid,k);
    else return query(rs[x],rs[y],mid+1,r,k-s);
}

int query(int x,int l,int r,int k){//查询树上有多少个数大于等于k,用于询问区间不同数的个数
    if(l==r) return k<=l?siz[x]:0;
    int mid=(l+r)>>1;
    if(k<=mid) return siz[rs[x]]+query(ls[x],l,mid,k);
    else return query(rs[x],mid+1,r,k);
}


//////////////////////////////////////////////////////////////////////////////////////////



//树状数组套主席树
int ls[maxn*20*20],rs[maxn*20*20],siz[maxn*20*20];
int rt[maxn],Tl[maxn],Tr[maxn],Tl_,Tr_,tot;

// n-> 树状数组节点个数     maxval->主席树叶子结点
// for(int j=x;j<=n;j+=j&-j) update(rt[j],1,maxval,pos,+1/-1); //注意pos写不要大常数
void update(int&u,int l,int r,int pos,int val){
    if(u==0) u=++tot;//,ls[u]=rs[u]=siz[u]=0;
    siz[u]+=val;
    if(l==r) return;
    int mid=(l+r)>>1;
    if(pos<=mid) update(ls[u],l,mid,pos,val);
    else update(rs[u],mid+1,r,pos,val);
}

//query(x-1,y,1,maxval,z)
int query(int x,int y,int l,int r,int k){
    Tl_=Tr_=0;
    for(int i=x;i;i&=i-1)Tl[Tl_++]=rt[i];
    for(int i=y;i;i&=i-1)Tr[Tr_++]=rt[i];
    while(l<r){
        int sum=0, mid=(l+r)>>1;
        for(int i=0;i<Tl_;i++) sum-=siz[ls[Tl[i]]];
        for(int i=0;i<Tr_;i++) sum+=siz[ls[Tr[i]]];
        if(k<=sum) {
            for(int i=0;i<Tl_;i++) Tl[i]=ls[Tl[i]];
            for(int i=0;i<Tr_;i++) Tr[i]=ls[Tr[i]];
            r=mid;
        }
        else{
            for(int i=0;i<Tl_;i++) Tl[i]=rs[Tl[i]];
            for(int i=0;i<Tr_;i++) Tr[i]=rs[Tr[i]];
            l=mid+1;
            k-=sum;
        }
    }
    return l;
}
//////////////////////////////////////////////////////////////////////////////////////////



int ls[maxn*20],rs[maxn*20],siz[maxn*20];
int tot,rt[maxn];
struct star{int v,nex;}g[maxn<<1];
int head[maxn],g_;
int w[maxn],fa[maxn][20],dep[maxn];

//tree
void ini(int n){
    g_=0;
    memset(head,-1,(n+1)*sizeof(head[0]));
}
void add_edge(int u,int v){
    g[g_].v=v;
    g[g_].nex=head[u];
    head[u]=g_++;

    g[g_].v=u;
    g[g_].nex=head[v];
    head[v]=g_++;
}

//lca
void build_lca(int cur=1,int father=0){
    dep[cur]=dep[father]+1;
    fa[cur][0]=father;
    for (int i=1;i<20;i++) fa[cur][i]=fa[fa[cur][i-1]][i-1];
    for(int i=head[cur];~i;i=g[i].nex){
        if(g[i].v==father)continue;
        build_lca(g[i].v,cur);
    }
}
int lca(int u,int v){
    if(dep[u]>dep[v])swap(u,v);//so dep[u]<dep[v]
    for(int i=19;i>=0;i--){
        if(dep[v]-(1<<i)>=dep[u])v=fa[v][i];
    }
    if(u==v)return u;
    for(int i=19;i>=0;i--){
        if(fa[u][i]!=fa[v][i]){
            u=fa[u][i];
            v=fa[v][i];
        }
    }
    return fa[u][0];
}

//seg tree
void update(int pre,int&u,int l,int r,int pos){
    u=++tot;
    ls[u]=ls[pre],rs[u]=rs[pre];
    siz[u]=siz[pre]+1;
    if(l==r)return ;
    int mid=(l+r)>>1;
    if(pos<=mid) update(ls[pre],ls[u],l,mid,pos);
    else update(rs[pre],rs[u],mid+1,r,pos);
}
void build_seg(int cur=1,int fa=0){//root
    update(rt[fa],rt[cur],1,disc_,w[cur]);
    for(int i=head[cur];~i;i=g[i].nex){
        if(g[i].v==fa)continue;
        build_seg(g[i].v,cur);
    }
}
// query(rt[u],rt[v],rt[lca],rt[fa[lca][0]],1,maxval,kth);
int query(int u,int v,int lca,int fa,int l,int r,int k){
    if(l==r)return l;
    int s=siz[ls[u]]+siz[ls[v]]-siz[ls[lca]]-siz[ls[fa]];
    int mid=(l+r)>>1;
    if(k<=s) return query(ls[u],ls[v],ls[lca],ls[fa],l,mid,k);
    else     return query(rs[u],rs[v],rs[lca],rs[fa],mid+1,r,k-s);
}
//////////////////////////////////////////////////////////////////////////////////////////