P3919 【模板】可持久化数组（可持久化线段树/平衡树）题解

程序员文章站 2022-07-14 08:40:40

...

博客园同步

原题链接

前置知识：

线段树区间询问 / 修改

简要题意：

维护历史版本上的询问，修改。

首先，如果只有 $1$ 个版本（即保证 $v_i = 1$ ），那么我们可以用 朴素的线段树 解决。 ~~题目没给这个部分分你怎么说呢~~

那么，一种思路就有了：

既然是 $m$ 个历史版本，我就先开 $m$ 个一模一样的线段树。然后每次修改都是 $O(\log n)$ ，查询就到对应的线段树上去查。

~~理想是美好的，但现实是残酷的~~

有没有想过一个问题：~~这样子能实现我还要主席树干什么啊~~ 一棵线段树的空间复杂度是 $O(n \log n)$ . $m$ 棵线段树的空间复杂度是 $O(nm \log n)$ . 然后你看到内存才 $500 \text{MB}$ 于是果断放弃了这个思路。

（ $\frac{4 \times (10^6)^2}{1024^2}$ ，大概 只需要 $3.8 \times 10^6$ 个 $\text{MB}$ 啊，你可以试一试）

但是，线段树里有这样一个思想：

既然没人询问我，我就偷懒。

那么，你可能会说，好，我版本不开，等你询问再开。

那它一个个询问过来你不还是死？

但是，你发现一个问题：

这 $m$ 棵线段树有着极高的相似度！

因为一开始它们都是一样的，然后每次修改只修改 一个版本的一个值。

一个思路来了：我们可以尝试把 $m$ 棵线段树开成一棵新的 “总线段树”，对相同的节点公用，对不同的节点分别开。

~~真是个好思路，可惜难以实现~~

确实，这就是 主席树 的由来。

主席树，又称可持久化线段树，可持久化数组，是一种高效的维护历史版本（可持久化）的一种数据结构。因为一个叫做 $\texttt{HJT}（黄嘉泰）$ 的人发明了该数据结构，然后 $\texttt{HJT= Hu Jing Tao}$ 正好是某主席之名，故得名。（偶然，纯属偶然）

没错，主席树就是这样子建的。

但是，直觉告诉我们，很多线段树共有一些节点有以下问题：

不能用 $\text{i*2 , i*2+1}$ 表示 $i$ 号节点的儿子节点。
每个节点不止有一个父亲。
主席树不止有一个根。
每个根都可以往下构成一棵线段树。

具体的，来看一棵主席树的图。

注：转载至 hyfhaha 的洛谷博客的一张图。

P3919 【模板】可持久化数组（可持久化线段树/平衡树）题解

这个图真形象。~~尤其是旁边的文字~~

但是，建树、查询、修改明显比线段树难多了 ~~这也许就是，线段树模板绿题，这题是紫题的原因吧~~ 。

研究建树：

你发现应该先搞一棵空树，它的根叫做 $T_0$ ，然后每建一棵线段树只需要增加 $\log n$ 的空间（因为只需要改一个路径对吧），注意细节。 ~~最讨厌题解里注意细节四个字~~

时间复杂度： $O(n \log n)$ .

inline int build_tree(int i,int l,int r) {
//	printf("%d %d %d\n",i,l,r);
	i=++f; if(l==r) { //f 表示当前节点编号
		t[i].num=a[l]; return f;
	} int mid=(l+r)>>1;
	L=build_tree(L,l,mid);
	R=build_tree(R,mid+1,r);
	return i; //正常建树
}

下面我们看修改。

修改的话，只需要在对应的线段树（即 $T_{v_i}$ ）上进行，与线段树本身代码相仿。

时间复杂度（单次）： $O(\log n)$

inline int ins(int i) {
	t[++f]=t[i]; return f;
} //新建节点
//它不问我就不建，这是懒的最高境界

inline int update(int i,int l,int r,int x,int y) {
//	printf("%d %d %d\n",i,x,y);
	i=ins(i); if(l==r) {t[i].num=y; return i;}
	int mid=(l+r)>>1;
	if(x<=mid) L=update(L,l,mid,x,y);
	else R=update(R,mid+1,r,x,y);
	return i; //基本同线段树
}

其本质在于，懒是有层次的，一直懒叫懒惰成性，一时懒叫劳逸结合。（？？？）

那么询问区间和怎么办？直接去对应的子树搞。

单次时间复杂度： $O(\log n)$ .

inline int query(int i,int l,int r,int x) {
//	printf("%d %d\n",i,x);
	if(l==r) return t[i].num;
	int mid=(l+r)>>1;
	if(x<=mid) return query(L,l,mid,x);
	else return query(R,mid+1,r,x);
} //同线段树

嗯，然后 主席树 的基本思路就到这里了。

总时间复杂度： $O(n \log n + m \log n)$ .

实际得分： $100pts$ .

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;

const int N=1e6+1;
#define L t[i].l
#define R t[i].r

inline int read(){char ch=getchar();int f=1;while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}
	int x=0;while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}

struct tree {
	int l,r,num;
};
tree t[N<<4]; int a[N];
int n,m,root[N<<4],f=0;

inline int ins(int i) {
	t[++f]=t[i]; return f;
}

inline int build_tree(int i,int l,int r) {
//	printf("%d %d %d\n",i,l,r);
	i=++f; if(l==r) {
		t[i].num=a[l]; return f;
	} int mid=(l+r)>>1;
	L=build_tree(L,l,mid);
	R=build_tree(R,mid+1,r);
	return i;
} //建树

inline int update(int i,int l,int r,int x,int y) {
//	printf("%d %d %d\n",i,x,y);
	i=ins(i); if(l==r) {t[i].num=y; return i;}
	int mid=(l+r)>>1;
	if(x<=mid) L=update(L,l,mid,x,y);
	else R=update(R,mid+1,r,x,y);
	return i;
} //修改

inline int query(int i,int l,int r,int x) {
//	printf("%d %d\n",i,x);
	if(l==r) return t[i].num;
	int mid=(l+r)>>1;
	if(x<=mid) return query(L,l,mid,x);
	else return query(R,mid+1,r,x);
} //查询

int main(){
	n=read(),m=read();
	for(int i=1;i<=n;i++) a[i]=read();
	root[0]=build_tree(0,1,n); //先建一棵树
	for(int i=1;i<=m;i++) {
		int op=read(),x=read(),y=read(),k;
		if(x==1) {
			k=read();
			root[i]=update(root[op],1,n,y,k); //每次多建一棵
		} else {
			printf("%d\n",query(root[op],1,n,y));
			root[i]=root[op]; //多建一棵
		}
	}
	return 0;
}

下一篇： 83. Remove Duplicates from Sorted List

P3919 【模板】可持久化数组（可持久化线段树/平衡树）题解