主席树

发表于 | 分类于 |

主席树是可持久化线段树的一种实现。

可持久化线段树：保存历史记录的线段树。

主席树来源：某大神考场上不会打某数据结构而发明的 Orz

如果更新某线段树要记录它的历史记录，最暴力的方法就是新开一棵线段树。

时间空间明显都很大。

不难发现，每次进行修改一个点时，线段树都只会修改某条路径上$log_2n$个点，如果新开线段树全都再复制一遍就太不划算了。

那我们可以试着只给要修改的那条路径开新空间。

以线段树经典用法求区间最大为例，如图：

将区间$[1,2,3,4]$中的$1$改为$5$

主席树

给要修改的点重开一个空间，不用修改的直接连回原来位置就好啦。

实现

不同时候的根节点的位置都不同，所以用一个$root$数组保存不同时间根节点的位置，$root[i]$表示修改第$i$个数后根节点的位置。

从根节点往下搜的时候，当前节点肯定是要重新开空间的。

对于当前节点不用修改的那个儿子，指针直接指回原来那个儿子的位置。对于需要修改的儿子，指针就要指向新开的空间的位置。

更新函数代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
TREE *update(int l,int r,int f,TREE *k)
{
	int N=++tl;           //开新空间
	if(l==r)
	{
		tree[N].sum=k->sum+1;
		return &tree[N];
	}
	int mid=(l+r)/2;
	if(f<=mid)
	{
		tree[N].l=update(l,mid,f,k->l);   //左儿子被修改
		tree[N].r=k->r;
	}
	else
	{
		tree[N].l=k->l;
		tree[N].r=update(mid+1,r,f,k->r);  //右儿子被修改
	}
	tree[N].sum=tree[N].l->sum+tree[N].r->sum;
	return &tree[N];        //返回当前节点位置，以便父亲节点操作
}

其他

可持久化线段树拥有很多普通线段树不具有的特殊性质，所以也有了很多乱七八糟的用法。因此，可持久化线段树的题目都不会是裸体，都值得思考。

例题：BZOJ2809 (题解戳这)