P3919 【模闆】可持久化數組 -初步探究主席樹

本篇blog主要是給自己（大家）看的。

感謝longlongzhu123奆佬（此人初二LCT）的指點，使本蒟蒻可以快速開始主席樹入門。

what is 主席樹？

$ \ \ \ \ \ \ \ $主席樹這個名字隻不過是OIer們在思考政(zhe)治(xue)的時候發明的好(du)聽(liu)的名字。其實主席樹的大名叫“可持久化線段樹”，一聽這名字就知道主席樹很毒瘤，是以他的發明者叫黃嘉泰（hjt* * *(什麼鬼啊?)）。

分步了解“可持久化線段樹”

$ \ \ \ \ \ \ \ $首先我們先來了解人盡皆知的小名“主席樹”，我們可以先看到“主席”這兩個字，嗯，很好，很霸氣，讀起來朗朗上口，是以我們可以知道主席樹是一個很霸氣的東西，以上扯淡。再來看“樹”，從這個字我們可以看出主席樹的本質是一棵樹，那是一棵什麼樹，結什麼果呢，下面看主席樹的大名“可持久化線段樹”。

$ \ \ \ \ \ \ \ \(看“可持久化”這四個字，很好了解，主席樹十分**持久**，因為它可持久化。那什麼叫持久呢，“可持久化”定義：可以支援回退，通路之前版本的資料結構；支援回退操作的意思就是可以通路未經過其他操作的版本，也就是說傳回到了以前的版本。那麼我們繼續看“線段樹”這幾個字眼，十分熟悉！相信大家肯定學過線段樹，如果沒學過\)\color{red} \large \text{線段樹}$的話，那就可以跳過這篇blog了。我們可以知道主席樹是基于線段樹的一種資料結構WOW。

$ \ \ \ \ \ \ \ $綜上所述，主席樹是一種霸氣的，持久的，基于線段樹的資料結構。

主席樹基本原理

$ \ \ \ \ \ \ \ $前文說了，線段樹與主席樹的本質是一樣的，隻不過主席樹可持久化，那麼難點就在于怎麼支援可持久化。

$ \ \ \ \ \ \ \ $我們想要支援回退操作就可以對每一次修改操作都進行一次複制，将未進行操作的線段樹版本進行複制，再對原線段樹版本進行修改，那麼我們就可以通路到舊版本的線段樹了。不過現在問題來了，這樣的空間複雜度将會乘上一個m，變成O(n*m)。不用說，肯定會陷入mle中不可自拔。

$ \ \ \ \ \ \ \ $那我們來分析一下單點修改的線段樹：

$ \ \ \ \ \ \ \ $我們發現隻有橙顔色經過的結點才被修改過。那麼我們就可以思考，我們可不可以隻對這些節點進行修改呢？答案當然是可以的，主席樹的基本思想就是隻對進行修改的結點進行複制。那麼主席樹是長什麼樣子的呢，下面一起來看一下吧。

$ \ \ \ \ \ \ \ $看着怎麼惡心的圖，相信大家還是可以發現這個圖中主席樹的一些性質：

1、每一次修改增加的節點個數為log(n)。

2、增加的非葉子結點會連向一個是其他版本的節點，一個是連向新節點。

3、主席樹有很多根……

4、對于每一個根都可以構成一棵完整的線段樹。

5、每一個節點都有可能有不隻一個爸爸……

$ \ \ \ \ \ \ \ $是以我們可以知道主席樹隻會對部分節點進行複制，并且每一次複制的節點個數是log(n)。我們每一次想詢問一個版本的線段樹，就可以在那個版本的根構成的線段樹中詢問。

但同時也延伸出許多問題：

1、怎麼建構新節點？怎麼給新節點編号？怎麼連邊？

2、怎麼通路子節點？

3、怎麼存根？

$ \ \ \ \ \ \ \ $很明顯這些問題線上段樹中完全不會出現，我們可以感覺到主席樹在建樹的代碼中會和線段樹不同。

現在給出剛才問題的答案：

1、直接開一塊記憶體池存新節點。編号為此時總節點數個數+1。開結構體存子節點編号；線段樹建什麼邊，一指了事。

2、通路子節點編号，不是像線段樹一樣乘2或乘2+1，而是在結構體存子節點編号。

3、另外開個數組存。

代碼主要和線段樹差不多，下面就看代碼吧。

代碼 P3919 【模闆】可持久化數組

是以我們定義一個節點要存三個資訊：左兒子，右兒子，權值

struct kkk{
	int l,r,val;
}tree[maxn];
           

建立節點：

int clone(int node){
	top++;
	tree[top]=tree[node];//全部資訊都傳到新節點
	return top;
}
           

建樹其實就是建立節點的過程：

int maketree(int node,int begin,int end){
	node=++top;
	if(begin==end){
		tree[node].val=a[begin];
		return top;
	}
	int mid=(begin+end)>>1;
	tree[node].l=maketree(tree[node].l,begin,mid);
	tree[node].r=maketree(tree[node].r,mid+1,end);
	return node;
}
           

更新和線段樹很像：

int update(int node,int begin,int end,int x,int val){
	node=clone(node);	//更新就要建立節點 
	if(begin==end){
		tree[node].val=val;
	}else{
		int mid=(begin+end)>>1;
		if(x<=mid)
			tree[node].l=update(tree[node].l,begin,mid,x,val);	//通路左子樹 
		else
			tree[node].r=update(tree[node].r,mid+1,end,x,val);	//通路右子樹 
	}
	return node;
}
           

詢問也一樣：

int query(int node,int begin,int end,int x){
	if(begin==end){
		return tree[node].val;
	}else{
		int mid=(begin+end)>>1;
		if(x<=mid)
			return query(tree[node].l,begin,mid,x);	//通路左子樹 
		else
			return query(tree[node].r,mid+1,end,x);	//通路右子樹 
	}
}
           

那麼主席樹的操作部分就寫完了QwQ

再來看主程式，裡面看根怎麼存儲：

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	root[0]=maketree(0,1,n);	//root[i]為i版本的根編号，剛開始編号為0 
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&rt,&mode,&x);
		if(mode==1){
			scanf("%d",&y);
			root[i]=update(root[rt],1,n,x,y);	//儲存版本 
		}
		else{
			printf("%d\n",query(root[rt],1,n,x));	//輸出 
			root[i]=root[rt];					//建立版本 
		}
	}
}
           

那麼這道題就寫完了。（其實我覺得一看圖就懂了，代碼什麼的都是假的）

點贊嗷 ~ \ QwQ / *