主席树（可持久化线段树）学习笔记

~~顾名思义，主席树就是主席想出来的一种数据结构。~~

经典例题

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

主席树，大名“可持久化线段树”。线段树大家都知道，“可持久化”即为可以访问某一版本下的树。

很容易想到，可以开 $m$ 棵线段树来实现可持久化线段树，可是这样的空间复杂度太高了，达到了 $O(4nm)$ 。

但是容易发现，每一次单点更新操作，最多只会有 $O(logn)$ 个节点被更改。所以对于每次单点更新操作，可以只新建出 $O(logn)$ 个节点，以节省空间。

例如这是一颗线段树：（第一个数代表版本号，第二、三个数代表区间）

假设我们需要修改位置 3 那么就需要新增一些节点：

假设我们又需要修改位置 5 那么又需要新增一些节点：

~~所以主席树这玩意根本不是树嘛……~~

怎么样，这种沿用旧节点的思想是不是很奇妙 awa。

可持久化线段树的难点主要在修改，查询基本和线段树是一样的，只不过多了版本号，需要记下每个版本对应的根节点。

给出模板题代码：

#include <iostream>
#include <cstdio>

#define S 1000005

using namespace std;

struct node
{
	int l,r,num;
}tree[S*20];

int n,m,cnt,a[S],r[S];

void built(int &now,int l,int r)
{
	if(l==r)
	{
		tree[++cnt].num=a[l];
		now=cnt;
		return;
	}
	int mid=l+r>>1;
	now=++cnt;
	built(tree[now].l,l,mid);
	built(tree[now].r,mid+1,r);
}

void upd(int &now,int las,int l,int r,int wh,int val)
{
	tree[++cnt]=tree[las];
	now=cnt; 
	if(l==r)
	{
		tree[now].num=val;
		return;
	}
	int mid=l+r>>1;
	if(wh<=mid)
	{
		upd(tree[now].l,tree[las].l,l,mid,wh,val);
	}
	else
	{
		upd(tree[now].r,tree[las].r,mid+1,r,wh,val);
	}
}

int que(int now,int l,int r,int wh)
{
	if(l==r)
	{
		return tree[now].num;
	}
	int mid=l+r>>1;
	if(wh<=mid)
	{
		return que(tree[now].l,l,mid,wh);
	}
	else
	{
		return que(tree[now].r,mid+1,r,wh);
	}
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	built(r[0],1,n);
	for(int i=1;i<=m;i++)
	{
		int v,type,pos;
		scanf("%d%d%d",&v,&type,&pos);
		if(type==1)
		{
			int val;
			scanf("%d",&val);
			upd(r[i],r[v],1,n,pos,val);
		}
		else
		{
			printf("%d\n",que(r[v],1,n,pos));
			r[i]=r[v];
		}
	}
	return 0;
}