Nemlit 的博客

Nemlit 的博客

By a konjac

可持久化线段树 1(主席树)

posted on 2019-01-25 20:45:57 | under 题解 |

更多主席树内容可见原文

PS:由于篇幅较长,只给出模板题代码,其他代码详见上述连接

主席树,一个数据结构,能访问到历史版本的数据,常用于可持久化和区间k大值,是线段树的一个升级版。

可持久化

可持久化的意思是可以访问任意版本的数据,一眼想到的暴力做法就是开n个数组来记录,这显然是不可取的。

那么我们考虑优化。若只有单点修改,不难发现每两个版本的差别最多为1,那么我们是不是可以只更改只一个数呢?

显然是可以的。在线段树上,我们每访问到一个节点,如果该节点没有被修改,直接用指针指想该节点即可(和动态开点线段树类似)

要注意的是,我们不能像以前一样用 $k*2$ 表示左儿子, $k*2+1$ 表示右儿子了(如果你用动态开点就当我没说),而是要用指针来访问左右儿子。

那我们怎么访问每一个版本呢?我们只需要对每一个版本存储一个根节点,从根节点访问就行了

这样我们就可以很好的来处理可持久化的问题了。

例题1-可持久化数组

直接采用上述方法,维护每一个版本的root即可

有了可持久化数组,那么我们便可以操作其他可持久化数据结构,如可持久化并查集

例题2-可持久化并查集

我们把每一个版本的fa数组记录下来,就可以很好的查询历史版本了。我们发现对于每次合并,fa数组只会修改一个(不能用路径压缩,因为路径压缩一次会修改很多值),所以我们直接用上述方法做就行了。

如果直接修改,那么单次复杂度可能退化成O(n),所以我们可以用启发式合并或按秩合并

区间k大

我们知道权值线段树是可以求全局k大的,那么我们可不可以用权值线段树来实现区间k大呢?

显然是可以的。我们可以先考虑1~l区间的k大。

我们给每一个点开一颗前缀的权值线段树,那么我们就可很容易的求出1~l的第k大值了。但是常规做法显然会炸空间,所以我们采用可持久化的方法来动态开点

那么区间k大怎么做呢?

这就要用到权值线段树的可减性。(权值线段树维护的是每个元素的出现个数,这显然是可减的)

于是对于段区间,我们看成连段区间相减就行了。

例题2-可持久化线段树

代码如下

#include<bits/stdc++.h>
using namespace std;
#define re register
#define il inline
il int read()
{
    re int x=0,f=1;re char c=getchar();
    while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();
    return x*f;
}
#define maxn 200005
struct node
{
    int l,r,val;
}e[maxn*20];
int n,m,root[maxn],cnt,b[maxn],a[maxn],co;
il void build(int &k,int l,int r)
{
    k=++cnt;
    if(l==r) return;
    int mid=(l+r)>>1;
    build(e[k].l,l,mid),build(e[k].r,mid+1,r);
}
il void change(int &k,int kk,int l,int r,int ll)
{
    k=++cnt; e[k]=e[kk]; e[k].val++;
    if(l==r) return;
    int mid=(l+r)>>1;
    if(ll<=mid) change(e[k].l,e[kk].l,l,mid,ll);
    else change(e[k].r,e[kk].r,mid+1,r,ll);
}
il int query(int ll,int rr,int l,int r,int k)
{
    int x=e[e[rr].l].val-e[e[ll].l].val;
    if(l==r) return b[l];
    int mid=(l+r)>>1;
    if(x>=k) return query(e[ll].l,e[rr].l,l,mid,k);
    return query(e[ll].r,e[rr].r,mid+1,r,k-x);
}
int main()
{
    n=read(),m=read();
    for(re int i=1;i<=n;++i) a[i]=b[i]=read();
    sort(b+1,b+n+1);//排序
    co=unique(b+1,b+n+1)-b-1;//去重
    build(root[0],1,co);
    for(re int i=1;i<=n;++i)
    {
        int now=lower_bound(b+1,b+co+1,a[i])-b;//意思是找到和a[i]相等的b,这样做的目的是保证所有的相等的全值都能保证被分到一个下标
        change(root[i],root[i-1],1,co,now);//因为是前缀权值线段树,所以在前一刻子树的基础上修改
    }
    while(m--)
    {
        int l=read(),r=read(),k=read();
        printf("%d\n",query(root[l-1],root[r],1,co,k));
    }
    return 0;
}

不那么模板的模板题

这题是强制在线,所以不能用整体二分等离线做法水过去,所以我们用主席树。

拓展到了树上,所以我们可以进行dfs,把上一题的建树过程改成change(root[i],root[fa[i]],1,co,now)即可

最后统计答案,我们不能直接用r的权值线段树-l的权值线段树,而使用l+r-lca(l,r)-fa[lca(l,r)](这里表示权值线段树),正确性类似于树上差分,在此不再赘述。

由于要求LCA,且要用dfs,所以我直接用树剖来求lca,将树剖的dfs1和要求的dfs合并在一起就行了。