@dxbdly 2021-12-26T07:24:27.000000Z 字数 4404 阅读 183

G2020 19寒假集训Day5

信息学——19寒假集训

G2020 19寒假集训Day5
- 一. 主席树

今天是G2020寒假集训Day5，主要讲数据结构中的主席树与平衡树

前置芝士点：线段树，BST树

PS：此文章默认已学线段树，BST树等简单的数据结构。

一. 主席树

1.定义

主席树，又称可持久化线段树，线段树大家都不陌生，那么什么是可持久化呢？

可持久化：可以支持回退，访问之前历史版本的数据结构

所以说主席树就是：

可以访问历史版本的线段树！

2.主席树的思想

先来看题：题面

我们会发现，此题要求在历史版本上查询或修改，首先很容易想到一种解法：

$1^o$ 暴力

开个二维数组，将每个历史版本都存下来，操作时直接访问历史版本即可，空间复杂度 $O(M^2)$ ，时间复杂度 $O(n^2)$

显然不行

$2^o$ 暴力优化

我们在暴力上进行优化，将二维数组改成M个链表。

我们容易发现在修改下标之后当前版本与历史版本完全相同

所以，我们可以将修改元素之前的 $\operatorname{copy}$

修改元素之后的直接将指针指向历史版本即可。

但此算法仍可以被卡掉，如果我的修改永远在最后一个，时间复杂度仍为 $O(n^2)$

$3^o$ 主席树

对上面的思想进行分析，我们会发现:

由于此题只需要单点修改，单点查询。

如果对应到一颗线段树上，那么修改与查询均只与叶节点有关

我们思考能不能引用前面的优化思想，将其运用到线段树上？

于是，可持久化线段树(主席树)诞生了！

主席树的思想：

对于不包含需修改节点的子树，我们直接用指针指向历史版本。

对于包含需修改节点的子树，我们暴力 $\operatorname{copy}$ 。

又因为对于线段树每一层，有且仅有一个节点子树包含需修改节点，而最多只有 $\log(n)$ 层

所以最多 $\operatorname{copy} \log(n)$ 次，单次时间复杂度 $O(\log n)$

成功解决!

$3.$ 主席树的实现

注意：

1.主席树需要动态开点，所以需要存下每个节点左，右儿子。

2.实现时并不需要设一个指针指向历史版本
而是存下了每个版本的根节点，并存下其左，右儿子是哪一个。

$1^o$ 建树

建树操作与线段树基本相同

代码：

//The code is from dxbdly
inline void build(int &i,int l,int r)//注意i需要随操作变化
{
    i=++tot;
    if (l==r)
       {
       tree[i].num=a[l];
       return ;
       }
    int mid=(l+r)>>1;
    build(tree[i].l,l,mid);
    build(tree[i].r,mid+1,r);
}

$2^o$ 修改

修改操作最重要的是确定哪些子树包含需要修改的节点。

我们可以考虑线段树的修改，由于是单点修改，所以每次修改时所遍历到的节点一定都包含待修节点，将其 $\operatorname{copy}$ 即可

代码：

inline void update(int &i,int v,int l,int r,int x,int val)
{
    copy(i,v);
    if (l==r)
       {
       tree[i].num=val;
       return ;
       }
    int mid=(l+r)>>1;
    if (x<=mid)
       update(tree[i].l,tree[v].l,l,mid,x,val);
    else
       update(tree[i].r,tree[v].r,mid+1,r,x,val);
}

$3^o$ 查询

查询操作也比较简单，确定历史版本所在根节点，直接找到所在历史版本的根节点，然后线段树查询即可。

inline int query(int i,int l,int r,int x)
{
    if (l==r)
       return tree[i].num;
    int mid=(l+r)>>1;
    if (x<=mid)
       return query(tree[i].l,l,mid,x);
    else
       return query(tree[i].r,mid+1,r,x); 
}

总时间复杂度 $O(mlogn)$

AC总代码

//The code is from dxbdly
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    bool f=0;
    while (!isdigit(c))
          f|=(c=='-'),c=getchar();
    while (isdigit(c))
          x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?-x:x;
}
int n,m;
struct node{
    int l,r,num;
}tree[20000005];
int a[20000005],tot;
int root[20000005];
inline void copy(int &i,int v)
{
    i=++tot,tree[i]=tree[v];
}
inline void build(int &i,int l,int r)
{
    i=++tot;
    if (l==r)
       {
       tree[i].num=a[l];
       return ;
       }
    int mid=(l+r)>>1;
    build(tree[i].l,l,mid);
    build(tree[i].r,mid+1,r);
}
inline void update(int &i,int v,int l,int r,int x,int val)
{
    copy(i,v);
    if (l==r)
       {
       tree[i].num=val;
       return ;
       }
    int mid=(l+r)>>1;
    if (x<=mid)
       update(tree[i].l,tree[v].l,l,mid,x,val);
    else
       update(tree[i].r,tree[v].r,mid+1,r,x,val);
}
inline int query(int i,int l,int r,int x)
{
    if (l==r)
       return tree[i].num;
    int mid=(l+r)>>1;
    if (x<=mid)
       return query(tree[i].l,l,mid,x);
    else
       return query(tree[i].r,mid+1,r,x); 
}
int main(){
    n=read(),m=read();
    for (register int i=1;i<=n;++i)
        a[i]=read();
    build(root[0],1,n);
    for (register int i=1;i<=m;++i)
        {
        int v=read(),op=read(),x,val;
        if (op==1)
           x=read(),val=read(),update(root[i],root[v],1,n,x,val);
        else
           x=read(),printf("%d\n",query(root[v],1,n,x)),root[i]=root[v];
        }
    return 0;
}

4.主席树的应用

来讲一下主席树的经典应用：区间第 $k$ 小。

题面

题解：

首先不管 $[l,r]$ 这个区间的第 $k$ 小如何求，我们先来想区间 $[1,r]$ 的第 $k$ 小如何求。

其实将上面说的主席树做一些改变即可：

将线段树改为权值线段树，对于每个[1,i]的区间建一个历史版本

将线段树改为权值线段树的话，我们可以这样操作。

查询时，对于当前点记他左儿子的个数为 $x$

若： $x\geq k$ ：则说明第 $k$ 小一定在左子树中
若： $x<k$ ：则说明第 $k$ 小一定在右子树中

对于第一种， $k$ 不变，递归左子树处理。
对于第二种， $k$ 变为 $k-x-1$ ，递归右子树处理。

那么我们就解决了 $[1,r]$ 区间的第 $k$ 小

对于 $[l,r]$ 区间的第 $k$ 小，由于我们维护的是n个权值线段树

所以我们可以在查询时可以通过区间减法

用 $[1,r]$ 的权值线段树 $-[1,l-1]$ 的权值线段树，即可得出 $[l,r]$ 的权值线段树。

而，权值线段树相减，只需要各个数字对应相减即可。

注意：数字过大，需要离散化。

//The code is from dxbdly
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    bool f=0;
    while (!isdigit(c))
          f|=(c=='-'),c=getchar();
    while (isdigit(c))
          x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?-x:x;
}
int n,m,len;
int a[5000005],ls[5000005],root[5000005];
struct node{
    int l,r,sum;
}tree[5000005];
int tot;
inline void copy(int &i,int v)
{
    i=++tot,tree[i]=tree[v],tree[i].sum++;
}
inline void build(int &i,int l,int r)
{
    i=++tot;
    if (l==r)
       return ;
    int mid=(l+r)>>1;
    build(i,l,mid);
    build(i,mid+1,r);
}
inline void update(int &i,int v,int l,int r,int x)
{
    copy(i,v);
    if (l==r) 
       return ;
    int mid=(l+r)>>1;
    if (x<=mid)
       update(tree[i].l,tree[v].l,l,mid,x);
    else
       update(tree[i].r,tree[v].r,mid+1,r,x);
}
inline int query(int u,int v,int l,int r,int k)
{
    if (l==r)
       return l;
    int mid=(l+r)>>1,x=tree[tree[v].l].sum-tree[tree[u].l].sum;
    if (x>=k)
       return query(tree[u].l,tree[v].l,l,mid,k);
    else
       return query(tree[u].r,tree[v].r,mid+1,r,k-x);
}
int main(){
    n=read(),m=read();
    for (register int i=1;i<=n;++i)
        a[i]=read(),ls[i]=a[i];
    sort(ls+1,ls+n+1);
    len=unique(ls+1,ls+n+1)-ls-1;
    build(root[0],1,len);
    for (register int i=1;i<=n;++i)
        {
        int x=lower_bound(ls+1,ls+len+1,a[i])-ls;
        update(root[i],root[i-1],1,len,x);
        }
    for (register int i=1;i<=m;++i)
        {
        int l=read(),r=read(),k=read();
        printf("%d\n",ls[query(root[l-1],root[r],1,len,k)]);
        }
    return 0;
}

G2020 19寒假集训Day5

一. 主席树

1.定义

2.主席树的思想

1^o 暴力

2^o 暴力优化

3^o 主席树

3. 主席树的实现

1^o 建树

2^o 修改

3^o 查询