【資料結構】淺談主席樹

前置知識

①線段樹

②權值線段樹

③桶的思想

④前綴和思想

（以上幾個前置知識我也希望我能有時間寫寫自己的博客講解一下【如果有時間的話嗚噫嗚噫~）

模板題

先上幾道模板題壓壓驚，有從別的博主那里piao來的，也有自己做到的~

因為深刻感受到了，要學習一個東西，最好還是先看看博客，看看思想，看看代碼實作

然后！拿著你熱乎的手敲模板去A它個幾道模板題考驗一下你的板子，再繼續深刻理解一下這個演算法的精髓，哦~完美！

P3919 【模板】可持久化線段樹 1（可持久化陣列）

P3834 【模板】可持久化線段樹 2（主席樹）

P1801 黑匣子

P5838 [USACO19DEC]Milk Visits G（這道題不算模板，但是還蠻有意思，maybe你模板題都寫過之后可以思考一下這道題，然后敲一敲檢驗一下自己是不是真的會了，這道題是dfs+lca+主席樹的，但是解法不僅限于這一種哦~【隊里大佬就有種超級巧妙超級厲害的解法dfs+lca就可以啦，下次有空也打算把題解寫寫博客~】）

主席樹的含義

主席樹就是可持久化線段樹，它是一種可持久化的資料結構，

那什么叫做可持久化的資料結構呢？

可持久化資料結構就是支持歷史詢問的資料結構，

比如一共有54115411次操作，我問你第251251次操作之后這個資料結構長啥樣，你能在約束的時間空間內回答出來就算支持了可持久化，否則就不算，

一種很××的做法就是每次更改構之后我都把它保存下來，然后你問哪次我就去哪次里面找就是了，但是這顯然在空間上非常不優秀，

然后前輩們發現，每次修改只會讓該資料結構某部分與之前不同，那就只需要記錄這不同的部分就行了，

——參考自淺談主席樹

能解決哪些問題

本質上是為了做 給你一個序列，每次修改后算一個新的版本，詢問某個版本中某個值 這個問題的，但是這個問題衍生開來可以演變出很多問題，比如很經典的主席樹模板題區間第k大問題，

主席樹的原理

普通的線段樹能夠維護當前狀態，而主席樹能夠維護 當前狀態+歷史狀態

我根據身邊老板的反應以及自己第一次接觸線段樹的感受，猜測應該很多人第一次聽到歷史狀態這個詞都會特別懵逼，那就舉個例子來具體說明吧~

栗子

比如有一個陣列，有n個數，分別是a~1~，a~2~，...，a~n~，有以下幾種操作：

只要修改一次陣列的值就會變成一個新的狀態（第一次更新后為第一個狀態，第二次更新后為第二個狀態，以此類推

①對第 i 個狀態進行單點修改，把第 i 個狀態時，第pos個位置變為k，

②查詢第 i 個狀態時，第pos個位置上的值，

像我們平時用線段樹做的題目，那都是在當前基礎上進行修改，這個基礎就是前面進行過的所有操作綜合的結果，要問你第某某次修改之后，第某某個結點的值，我想你必然是答不出來了，

暴力

現在我們先來想一個非常暴力的方法來解決這個想要在歷史版本上進行修改/查詢操作的問題吧~

既然我們可以做到在當前狀態下修改啊、查詢啊，說明對于修改查詢其實不是問題，我們對于當前狀態進行修改查詢需要一顆線段樹來維護，那對于上面提出的歷史版本的問題，我們就用好多好多顆線段樹就可以解決啦，

想象一下，你每修改一次（陣列發生改變）后，你就用一顆新的線段樹來保存修改后這個陣列的狀態，一棵線段樹對應一個歷史版本，那你需要在某個歷史版本上進行修改或者查詢操作的時候是不是只需要找到這個歷史版本對應的這棵線段樹，然后在這棵線段樹上操作就完事了，

當然，這樣問題倒是解決了，空間也是爆炸了，還是炸的稀碎的那種hhhhhhhh

那怎么優化呢？

空間優化（核心思想一）

那就要用到主席樹的第一個核心思想——空間優化

因為我們知道線段樹是一個二叉樹維護狀態，你每一次修改最多會修改掉logN個結點（N是整棵線段樹的節點總數），也就是修改掉從你修改的這個葉子結點一路往上走，走到根結點的這條鏈會發生變化，其他結點都沒有發生變化，因此每一次修改就只需要新建logN個結點供新的這棵線段樹使用，其他的結點跟之前的線段樹共用就可以啦，這樣是不是一下子就省了好多好多空間！

這樣，如果有m次修改，那 空間復雜度就是N+mlogN 的，是不是非常理想，非常誘人的一個空間復雜度！

（菜雞第一次自己正兒八經算空間復雜度，如有不對之處，還請各位大佬不吝賜教~）

圖解主席樹

舉個栗子說明一下剛剛說的空間優化的程序哈

序列 4 3 2 3 6 1

根據權值線段樹的思想，以值域作為線段樹的根結點的區間

建一棵如下圖的權值線段樹

一開始build完一棵初始的樹，都是空的，里面啥子都沒得，

然后開始把我們序列里的點一個一個插入進去，先插入第一個數4

首先，先新建一個點作為根節點，因為不管修改哪一個點，根節點一定會被修改掉，因為根節點是掌管整個值域的，

然后看看4是屬于原先那棵樹的哪個兒子呀——右兒子，所以我們要新建一個結點作為新的根節點的右兒子，左兒子沒有被修改，所以新的根結點跟之前版本的根結點共用一下就可以啦

遞回到下面也是同理哦，被修改了的話就新建一個，沒有的話就共用，nice！

插入第2個數 3 的時候是在已經插入了4這個數的基礎上修改，也就是在藍色點的基礎上修改，原理同上

同上

圖解大概就是這樣哦

甚至可以結合代碼來康康！可能會理解得更快一點我猜

圖源【學習筆記】主席樹

代碼實作

講完了主席樹的核心思想，就得講講代碼實作了，

個人學習主席樹最痛苦的經歷就是看不懂博主們的模板~嗚噫嗚噫

所以我覺得學會思想是一回事，把思想跟代碼結合起來理解就是另外一回事了

所以講代碼也是很重要的！

所以，我掏出了我四十米的大刀（啊呸，長長的主席樹板子

往上面加上了羅里吧嗦的注釋

希望能夠幫助各位理解吧

不過感覺這樣比較適合初學者理解代碼

用的時候這么多注釋好不優雅哦hhhhhhhhh

【忘記說了】這個板子是直接拉了一個模板題的代碼，大家可以根據這道題目理解康康

傳送門

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<iostream>
#include<map>
#include<queue>
#include<string>
using namespace std;
typedef long long ll;
const ll maxn=1e6+50;

struct node
{
	ll l,r,v;
}tree[maxn<<5];
//node是樹上的結點，l代表其掌管的區間的左邊界，r代表其掌管的區間的右邊界 

ll rt[maxn],sz=0;
//rt是記錄每個版本的那棵線段樹的根節點的陣列，rt[0]代表第0個狀態的線段樹的根節點的節點編號為rt[0]
//sz是記錄當前用了多少個結點的，也是每次新增結點時使用的變數~ 
ll a[maxn];//記錄初始陣列，初始建樹的時候用 
void build(ll &rt,ll l,ll r)//建樹 
{
	rt=++sz;//新建一個結點 
	if(l==r)
	{
		tree[rt].v=a[l];
		//碰到一個結點只掌管一個值的時候，
		//把初始值更新上去（講不太靈清，希望學過線段樹的大家都懂 
		//build函式跟普通線段樹沒什么區別 
		return;
	}
	ll mid=(l+r)>>1;
	build(tree[rt].l,l,mid);//建左子樹 
	build(tree[rt].r,mid+1,r);//建右子樹 
}

ll update(ll o,ll l,ll r,ll pos,ll k)//更新|在版本o上把pos這個位置的值更新為k
{
	ll oo=++sz;//新建一個節點作為這個新的狀態的根節點 
	tree[oo]=tree[o];//首先把原先的根結點整個賦給新的根節點 
	if(l==r)
	{
		tree[oo].v=k;//如果找到更新點則更新這個點的值 
		return oo;
	}
	ll mid=(l+r)>>1;
	if(mid>=pos)tree[oo].l=update(tree[oo].l,l,mid,pos,k);
	//判斷pos是否大于mid，若是則說明應該向這個結點的左子樹去更新 
	//同時也說明，會被改變的那條鏈是在左子樹上，因此是tree[oo].l=update(....)
	//根據update函式我們知道，該函式會回傳一個結點編號作為新建的結點給tree[oo].l 
	//tree[oo].r一開始是從原先的根結點接過來的，在這種情況下，右子樹不會發生改變，所以不需要更新，與原來的樹公用即可 
	else tree[oo].r=update(tree[oo].r,mid+1,r,pos,k);//同理 
	return oo;//把根結點的編號回傳
}

ll query(ll o,ll l,ll r,ll pos)//詢問|在版本o上查詢pos這個位置的值  
{
	if(l==r)return tree[o].v;//如果找到這個結點則回傳這個結點的值 
	ll mid=(l+r)>>1;
	if(mid>=pos)return query(tree[o].l,l,mid,pos);//如果pos這個位置>=mid則往左子樹去找 
	else return query(tree[o].r,mid+1,r,pos);//否則往右子樹去找
	//（這部分類似普通線段樹） 
}

int main()
{
	ll n,m;
	scanf("%lld %lld",&n,&m);
	for(ll i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);//初始序列放在A陣列里 
	}
	build(rt[0],1,n);//建樹 
	
	//這道題的歷史版本的解釋跟博客里說的不太一樣 
	//這道題目里讀入一個操作，無論是查詢還是更新， 
	//執行完這個操作之后就是一個新的狀態了 
	for(ll i=1;i<=m;i++)
	{
		ll v,op,pos,k;
		scanf("%lld %lld %lld",&v,&op,&pos);
		if(op==1)//更新操作 
		{
			scanf("%lld",&k);
			rt[i]=update(rt[v],1,n,pos,k);//在版本v上把pos這個位置的值更新為k 
		}
		else//查詢操作 
		{
			rt[i]=rt[v];
			printf("%lld\n",query(rt[v],1,n,pos));//在版本v上查詢pos這個位置的值 
		}
	}
}

閑話家常

從某個博主那里看到，據說主席樹叫做主席樹的原因是發明它的人叫做黃嘉泰，縮寫HJT，因此得名主席樹~好有意思嘻嘻嘻嘻

聽說主席樹是有什么靜態啊，動態啊的，就暫時沒往后學了，先學到這里啦~

以后有空再補充哦~

聽說主席樹也是可以區間修改什么的，但是可能會比較復雜，復雜度什么也會比較高，不太經常用到，所以暫時也沒看先，

關于主席樹如何解決區間第k大問題，我想再寫一篇博客來講，所以靜待吧~

寫完會把鏈接放上來的~

參考博客

這些是我在學習主席樹的時候看的一些博客，可能會對你萌有用，就鏈在這里啦

其實也是為了自己以后還能找到它們，畢竟里面還有一些沒A過的模板題呢~

然后因為我個人是特別懶的，所以直接抓了博主們的圖來用，特此宣告~

【學習筆記】主席樹

主席樹入門詳解+題目推薦

淺談主席樹

主席樹詳解

主席樹 （動態）圖文講解讓你一次就懂 zoj2112為例

標籤：C++

上一篇：Qt與Js互動

下一篇：用C++實作：末尾0的個數