[算法学习笔记]主席树

· · 题解

0. 前言

出题出挂了，来好好学主席树了

前置知识

线段树

没了

1. 简介

对于使用线段树，我们可以较好地解决“带修改的全局第k大（或小）问题”。但是对于某个区间进行求第k大（或小）操作就不是那么容易了。

1.1 “可持久化”

可持久化一词在数据结构中十分常见。“可持久化”的意思就是“带有历史版本的”数据结构。而在我们所接触到的基本数据结构中（如数组、并查集、平衡树等）都有各自的可持久化版本。

1.2 主席树的引出

主席树，又名 “可持久化线段树”。至于为什么叫“主席树”我也不是特别明白。其基本状态就是一个可以查询多个历史版本的线段树。

1.3 模板题

P3834 【模板】可持久化线段树 1（主席树）

题目背景

这是个非常经典的主席树入门题——静态区间第 k 小

题目描述

如题，给定 n 个整数构成的序列，将对于指定的闭区间查询其区间内的第 k 小值。

输入格式

第一行包含两个正整数 n,m，分别表示序列的长度和查询的个数。

第二行包含 n 个整数，表示这个序列各项的数字。

接下来 mm 行每行包含三个整数 l,r,k , 表示查询区间 [l,r] 内的第 k 小值。

输出格式

输出包含 m 行，每行一个整数，依次表示每一次查询的结果

2. 主席树

2.1 朴素思想

根据上文所说，主席树就是带有历史版本的线段树。如果要维护历史版本，最普通的思想就是建立多个完整的线段树，并在其上面进行操作。

但是很明显这个方案是不可行的。对于一个时间复杂度在 O(nlogn) 级别上的算法来说，数据通常在 10^5 - 10^6。如果维护的历史版本过多，会导致空间复杂读过大(每个历史版本的空间都在 n<<2 即 n*4 的级别上)。

2.2 正解

对于每次修改，几乎没有对全局所有节点的修改。所以在进行修改时我们只需要将被修改的点建立一个新的“存档”就可以完成修改。

一般的我们只需要新建从根开始向下经过的每一个点就行了。（如下图所示）

2.3 模板题解决思路

模板题要求查询区间内第k小。根据以往经验我们可以选择运用“权值线段树”解决问题。

对于题目要求的区间查询，我们可以运用前缀和的思想解决问题，即用 [1,l-1] 中的数据与 [1,r] 中的数据做差得出区间内的“权值线段树”（而不用以爆炸的复杂度为每次询问建树）

2.3 代码实现（以模板题为例）

主席树的建立

对于主席树我们并不能像线段树那样通过公式（ls=now<<1,\ rs=now<<1|1）计算出其左右儿子的下标，所以我们就需要建立起数组（或结构体解决）记录节点信息

const int N=2e5+15;
int rt[N],ls[N<<5],rs[N<<5],sum[N<<5],tot;

然后就是建树了。

建树的时候对于模板题我们需要先建一个空的树，作为以后修改的基准点。

void build(int &o,int l,int r){
    o=++tot;
    if(l==r) return;
    int mid=(l+r)>>1;
    build(ls[o],l,mid);
    build(rs[o],mid+1,r);
}

（真的和线段树建树一模一样呢（大雾））

修改

我们知道，对于一颗树，如果想要从根访问某个叶子节点，我们需要经过一条链。由于在线段树的单点修改中，我们经过链上的点都需要被修改，所以我们只需要增加这一条链的副本即可。


inline int modify(int o,int l,int r,int p){
    int oo=++tot;
    ls[oo]=ls[o],rs[oo]=rs[o],sum[oo]=sum[o]+1;
    if(l==r) return oo;
    int mid=(l+r)>>1;
    if(p<=mid) ls[oo]=modify(ls[oo],l,mid,p);
    else rs[oo]=modify(rs[oo],mid+1,r,p);
    return oo;
}

模板题的查询

模板题的查询和线段树的基本相同。在查询的时候可以想象一颗线段树，每个节点的值是以 rt[r] 为根的线段树相应节点的值减去 rt[l-1] 为根的线段树相应节点的值（可以类比前缀合理解）

对于这样一个线段树就可以运用已有知识解决。

inline int query(int L,int R,int l,int r,int k){
    int ans,mid=(l+r)>>1,x=sum[ls[R]]-sum[ls[L]];
    if(l==r) return l;
    if(x>=k) ans=query(ls[L],ls[R],l,mid,k);
    else ans=query(rs[L],rs[R],mid+1,r,k-x);
    return ans;
}

3. 最重要的应用之一 —— 可持久化数组

主席树可以较好地维护一个“支持查询历史版本的”线段树，对于可持久化数组我们可以利用其支持历史版本的特点，实现可持久化

3.1 模板题

题目描述

如题，你需要维护这样的一个长度为 NN 的数组，支持如下几种操作

  1. 在某个历史版本上修改某一个位置上的值

  2. 访问某个历史版本上的某一位置的值

此外，每进行一次操作（对于操作2，即为生成一个完全一样的版本，不作任何改动），就会生成一个新的版本。版本编号即为当前操作的编号（从1开始编号，版本0表示初始状态数组）

输入格式

输入的第一行包含两个正整数 N,M, 分别表示数组长度和操作的个数

第二行包含 N 个整数，依次为初始状态下数组各位的值 (依次为 a_i, 1\leq i \leq N )

接下来 M 行包含 3 或 4 个整数，代表两种操作之一 (i 为基于的历史版本号)：

1.$ 对于操作 $1$ , 格式为 $ v_i\ 1\ loc_i\ value_i$ 即在版本 $v_i$ 的基础上， 将 $a_{loc_i}$ 修改为 $value_i 2.$ 对于操作 $2$ , 格式为 $ v_i\ 2\ loc_i\ $ 即访问版本 $v_i$ 中 $a_{loc_i}$ 的值， 生成一样版本的对象应为 $v_i

输出格式

输出包含若干行，依次为每个操作 2 的结果。

3.2 解决思路

利用主席树解决

我们可以原数组存放在rt[0]的树的叶子节点，对于每一次修改直接修改即可

3.3 代码

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<algorithm>
#include<cmath>
#include<queue>

using namespace std;

#define rg register
#define ll long long
#define ull unsigned long long

namespace Enterprise{

    inline int read(){
        rg int s=0,f=0;
        rg char ch=getchar();
        while(not isdigit(ch)) f|=(ch=='-'),ch=getchar();
        while(isdigit(ch)) s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
        return f?-s:s;
    }

    const int N=1e6+15;
    int val[N<<5],rt[N],ls[N<<5],rs[N<<5],a[N],tot;
    int n,m;

    inline int build(int l,int r){
        int o=++tot;
        if(l==r){ val[o]=a[l];return o; }//遍历到叶子节点赋值
        int mid=(l+r)>>1;
        ls[o]=build(l,mid);
        rs[o]=build(mid+1,r);
        return o;
    }

    inline int change(int pre,int l,int r,int x,int v){
        int o=++tot;
        ls[o]=ls[pre],rs[o]=rs[pre],val[o]=val[pre];
        if(l==r){
            val[o]=v;//在叶子节点处修改
            return o;
        }
        int mid=(l+r)>>1;
        if(x<=mid) ls[o]=change(ls[pre],l,mid,x,v);
        else rs[o]=change(rs[pre],mid+1,r,x,v);
        return o;
    }

    inline int query(int now,int l,int r,int x){//与正常线段树单点查询无异
        if(l==r) return val[now];
        int mid=(l+r)>>1;
        if(x<=mid) return query(ls[now],l,mid,x);
        else return query(rs[now],mid+1,r,x);
    }

    inline void main(){
        n=read(),m=read();
        for(rg int i=1;i<=n;i++) a[i]=read();
        rt[0]=build(1,n);
        for(rg int i=1;i<=m;i++){
            int ver=read(),opt=read(),x=read();
            if(opt==1){
                int v=read();
                rt[i]=change(rt[ver],1,n,x,v);
            }else{
                rt[i]=rt[ver];//直接将当前版本节点编号赋成要求的版本编号。这样可以快捷地完成新建立一个和v_i相同的版本
                printf("%d\n",query(rt[ver],1,n,x));
            }
        }
    }
}

signed main(){
    Enterprise::main();
    return 0;
}

4. 主席树时空复杂度分析

4.1 时间复杂度

主席树的基本操作的线段树思想大体一致，时间复杂度也基本一致。

对于建树，时间复杂度为 O(nlogn)

由于这里查询和修改都是单点操作，所以时间复杂度为 O(logn)

所总体时间复杂度基本为 O((m+n)logn)

4.2 空间复杂度

对于 rt[0] 来说，空间复杂度=正常线段树空间复杂度，即最坏 O(4n)

对于每次修改，由于仅修改了 logn 个节点，所以所有新建版本的最坏复杂度为 O(mlogn)

4.3 小声bb

一般的对于所有节点及其对应值（如节点值，左右儿子等）我们可以开20倍空间，或者 maxn<<5 处理。 各位大佬肯定已经知道了。