可持久化线段树 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)$。

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

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

参考文献

结尾

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

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