算法

可持久化线段树 2

可持久化线段树

前言

这个东西之前讲过，但是用得少，很快就忘了。

我又看了我之前的那篇笔记，简直就是胡言乱语。所了解的太浅了。

最近在刷数据结构，于是决定再写一篇。

但是，之前那篇不打算删了，想看黑历史的可以去看。

算法概要

可持久——即可以保存历史版本。

我们如何得到一棵可以保存历史数据的树呢？最笨的方法就是每个操作之后都建一棵线段树。

如何优化？

发现我们可以共用前面建好的结构，无需重新建树。

主席树

主席树是可持久化线段树的一种，由黄嘉泰发明，因名字缩写而被称为主席树。

主席树一开始是用来处理区间第 $k$ 小的问题。

一句话概要思想：一棵权值线段树是由不在同一层的从根到叶子结点的链构成。

什么意思呢？

可以理解成一条时间轴将根节点穿起来，每个根节点都是一个历史版本的入口，每个历史版本都可以沿用以前的节点结构。

实现主席树——建树

难点其实就是建树，因为这与主席树的思想紧紧相关。

每次插入一个信息，就将它从根节点到叶子结点的这条链新建出来（权值线段树）。

当然，这条链上的节点都是新建，因为这是一个新的历史版本；其他节点就沿用以前的节点。

例 1 区间第 $k$ 小

P3834 【模板】可持久化线段树 2

怎么做呢？

我们可以按顺序插入数组中的每个元素。

这样的话就有 $n$ 个历史版本。

当我们想知道 $[l,r]$ 的第 $k$ 小时，我们可以只关注版本 $l-1$ 和版本 $r$。

这样的话，又因为这是棵权值线段树，所以可以通过当前节点的 $size$ 之差来判断第 $k$ 小在什么地方。

注意，本题不带修。

带修怎么办呢？看例 3。

code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int MAXN=2e5+5,INF=1e9;

int n,m,tot;
int a[MAXN];
int rts[MAXN];
struct TREE
{
    int lc,rc,sz;
}tr[MAXN<<5];

void pushup(int rt)
{
    tr[rt].sz=tr[tr[rt].lc].sz+tr[tr[rt].rc].sz;
}

void update(int &rt,int lst,int l,int r,int val)
{
    rt=++tot;
    tr[rt]=tr[lst];
    if(l==r)
        tr[rt].sz++;
    else
    {
        int mid=(l+r)>>1;
        if(val<=mid)
            update(tr[rt].lc,tr[lst].lc,l,mid,val);
        else
            update(tr[rt].rc,tr[lst].rc,mid+1,r,val);
        pushup(rt);
    }
}

int query(int r1,int r2,int l,int r,int k)
{
    if(l==r)
        return l;
    int lc1=tr[r1].lc,lc2=tr[r2].lc;
    int mid=(l+r)>>1;
    int tmp=tr[lc2].sz-tr[lc1].sz;
    if(tmp>=k)
        return query(lc1,lc2,l,mid,k);
    return query(tr[r1].rc,tr[r2].rc,mid+1,r,k-tmp);
}

signed main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        update(rts[i],rts[i-1],-INF,INF,a[i]);
    }
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        scanf("%lld%lld%lld",&x,&y,&z);
        printf("%lld\n",query(rts[x-1],rts[y],-INF,INF,z));
    }
    return 0;
}

例 2 可持续化数组

P3919 【模板】可持久化线段树 1（可持久化数组）

这个就是很简单的了，不用权值线段树。

首先对于原数组建线段树，称为历史版本 0。

然后对于 $m$ 次操作，每次都是一个历史版本；如果是查询操作，就复制前一个一模一样的。

剩下的就是中规中矩了，就是建一条链，其他节点就沿用。

code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

#include<bits/stdc++.h>
using namespace std;

// #define int long long
#define ls tr[rt].lc
#define rs tr[rt].rc

const int MAXN=2e6+5;

int n,m;
int a[MAXN],rts[MAXN*20];
struct HJT
{
    int lc,rc,val;
}tr[MAXN*20];
int tot;

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

void update(int &rt,int old,int l,int r,int x,int k)
{
	rt=++tot;
	tr[rt]=tr[old];
	if(l==r)
		return tr[rt].val=k,void();
	int mid=l+r>>1;
	if(x<=mid) update(ls,tr[old].lc,l,mid,x,k);
	else update(rs,tr[old].rc,mid+1,r,x,k);
}

int query(int rt,int l,int r,int x)
{
	if(l==r)
		return tr[rt].val;
	int mid=l+r>>1;
	if(x<=mid) return query(ls,l,mid,x);
	return query(rs,mid+1,r,x);
}

signed main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	build(rts[0],1,n);
	for(int i=1,old,op,x,k;i<=m;i++)
	{
		scanf("%d%d%d",&old,&op,&x);
		if(op==1)
		{
			scanf("%d",&k);
			update(rts[i],rts[old],1,n,x,k);
		}
		else
			printf("%d\n",query(rts[i]=rts[old],1,n,x));
	}
    return 0;
}

例 3 区间第 $k$ 小（带修）

首先你要知道树状数组是个什么东西。

这里要用到它的思想。

题面

给定一个长度为 $n$（$n \leq 50,000$）的数组 $a_1 , a_2 … ,a_n$ 和 $q$（$q \leq 10,000$）此询问，每次询问：

  1. Q i j k 表示区间 $[i,j]$ 中第 $k$ 小的数是多少，并输出这个数
  2. C i t 表示将第 $i$ 个数改为 $t$

Solution

首先考虑最笨的办法，就是修改这个历史版本后，它后面的所有版本都跟着改写。

怎么优化呢？

想起树状数组就是通过类树分区间管辖，所以可以做到 $O(\log n)$。

那这里也可以沿用这种思想，就是分区间管辖，每次改写就改写管辖他们的“大哥”，查询的时候在下放。

概要就是这么个概要，洛谷上没有这道题，我也不打算写代码（看起来很麻烦的样子），自己去写吧（雾）。

参考文献

结尾

先草草结束吧，可能未来还会写可持久化平衡树什么的，也不确保这次一定就完全掌握了主席树。

先这样吧，多卷题，时而温故而知新。