浅谈可持久化数据结构(一)

第一次接触可持久化这个概念是在学习主席树 (一种解决静态区间第 $K$ 大的数据结构) 的时候了解到的。
什么是可持久化数据结构?支持回到一个历史版本并回答一些在历史版本上的询问,支持从一个历史版本,通过响应操作扩展出另一个新的版本。简单来说就是,就是 能支持访问以往某个版本的数据的数据结构
可持久化是一种操作(思想?),并不单指某种数据结构。我所听过的还有,可持久化并查集,可持久化哈希树等等,这边文章以可持久化线段树来引入这个概念(或者说讲解主席树?)。

主席树由来

为啥叫主席树呢?传说发明这种数据结构的神犇黄嘉泰,因为他在考试的时候不会写归并树就写了主席树这种东西替代归并树,并成功让广大 $OIer$ 使用了这种数据结构,把归并树扔进了垃圾箱。因为他的名字缩写 $HJT$ 也是当时 $chairman$ 的名字缩写,故称为主席树。

在学习主席树之前,需要你很熟悉线段树这个东西,因为主席树的主体是多颗线段树。不会线段树的话点这里

问题描述

看这里

在学习主席树以前,先了解一下权值线段树

权值线段树

权值线段树,基于普通线段树,但是不同。
举个栗子:对于一个给定的数组,普通线段树可以维护某个子数组中数的和,而权值线段树可以维护某个区间内数组元素出现的次数,权值线段树的节点用来表示一个区间的数出现的次数。针对上面问题,我们通过对于每个节点进行构建权值线段树,构架方式如下。图片出处bestFy

7 1
1 5 2 6 3 7 4
2 5 3 

空树
然后对于每个节点,通过线段树的区间进行加 $1$

  • 插入 $1$
    插入1

  • 类似这样一直更新到结束

插入4

到这里对于上述序列一共构建了 $7$ 颗权值线段树。当我们要查询 $[2, 5]$ 内第 $3$ 大的数字时,我们只需要先取出 构建的第 $1$ 颗线段树, 与第 $5$ 颗线段树拿出来
第一颗

第五颗
把他们对应的区间进行相减, 就可以得到区间 $[2, 5]$ 内的数字出现的情况(前缀和的思想,类似于树状数组求区间和)。
区间内数字个数
查询这颗线段树, 可以保证, 左儿子的数值一定小于右儿子, 既然要查询区间第 $k$ 小, 优先判断左儿子内是否有 $k$ 个数字, 如果有那么继续在左儿子内查找,反之则在右儿子内查找第 $k -$ 左儿子中数字的次数。以图为栗,当我们查询第 $3$ 小时,判断左儿子 $[1, 4]$ 内只有两个数字,最多是 $2$小, 所以我们要在右儿子 $[5, 7]$中查找, 此时在左儿子中已经出现了两个数字, 代表已经有了两个小的数字, 此时在右儿子中只需要查找 $3-2$ 个出现的数字,判断 $[5,7]$内左儿子中数字出现的次数 $ >= 1 $,进入 $[5, 6]$区间, 判断此时 $[5, 6]$的左儿子中出现的次数$ >= 1 $,所以此时返回的线段树的 $L$, 即为要找的数字,一班该点代表的都是离散化后的结果, 所以只要把结果对应回原数组即可。

主席树

通过上面的方法,可以看出,这是一个非常浪费空间的方法,必然是不可取的,此时就要套用可持久化的概念,从一个历史版本,通过响应操作扩展出另一个新的版本,而非创建一个新的版本。准对与次,主席树空间进行了极大的优化,本节图片与栗子来自 Hypoc_
首先,要明确一下,主席树上每个节点的值的定义(设这个节点的管理范围为$[L, R]$,并且现在已经将这个数列离散化了):表示在当前前缀中,有多少个数的值在 $[L, R]$ 中。

比如下面这个序列${9,3,11,6}$,离散化后就是${3,1,4,2}$,针对每一个前缀进行建树(红色数字表示每个节点的值,意义如上所述)

  • 插入 3
    插入3

  • 插入 1,是在上一个前缀的基础上加
    插入1

  • 以此类推,可以得到下图
    最终

针对每一次修改,都只会影响到,一条链上的数值,我们只需要对这条链进行修改,其他链直接沿用即可。此时主席树就已经构建完成, 当我们要查询 $[L, R]$ 中 $k$ 小时,依然利用前缀和的思想即可求解。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 4e5 + 5;
const int INF = 0x3f3f3f3f;
int a[MAXN],root[MAXN],n,m,x,y,k,cnt;
vector<int> V;
struct Node {
    int l,r,sum;
} T[MAXN*20]; //主席树要开的更大

int getid(int x) { //离散化
    return lower_bound(V.begin(),V.end(),x) - V.begin() + 1;
}

void Update(int l,int r,int &x,int y,int pos) { //注意这个x, 每次更新x都在修改,对这条链进行标号修改
    T[++cnt] = T[y]; //对一条链上的数进行更新操作
    T[cnt].sum++;
    x = cnt;
    if(l == r)
        return ;
    int mid = (l + r) >> 1;
    if(pos <= mid) //与线段树的单点更新一样
        Update(l,mid,T[x].l,T[y].l,pos);
    else
        Update(mid+1,r,T[x].r,T[y].r,pos);
}

int Query(int l,int r,int x,int y,int k) {
    if(l == r)
        return l;
    int mid = (l + r) >> 1,sum = T[T[y].l].sum - T[T[x].l].sum;//判断区间[x, y]左儿子出现的了多少个树
    if(sum >= k) //如果够就往左,否则就往右 k - sum
        Query(l,mid,T[x].l,T[y].l,k);
    else
        Query(mid+1,r,T[x].r,T[y].r,k - sum);
}


int main() {
    int n;
    scanf("%d %d",&n,&m);
    for(int i = 1; i <= n; i++) {
        scanf("%d",&a[i]);
        V.push_back(a[i]);
    }
    sort(V.begin(),V.end()),V.erase(unique(V.begin(),V.end()),V.end());
    for(int i = 1; i <= n; i++)
        Update(1,n,root[i],root[i-1],getid(a[i]));
    while(m--) {
        scanf("%d %d %d",&x,&y,&k);
        printf("%d\n",V[Query(1,n,root[x-1],root[y],k)-1]); //把离散化的点对应回原数组
    }
    return 0;
}

最后

感觉写的不是很清楚,写一篇算法讲解远比写一篇题解难,推荐一下 $qsc$ 的视频,我当时的主席树就是看卿学姐学会的,代码的写法,离散化的写法都是看他的卿学姐, 同时感谢本文引用的图片栗子的作者。