主席樹的一點點學習體會，主席樹是一種可持久化的數據結構，第一次這麼深入的學習可持久化的數據結構，花了好幾天學習它包括他的前置知識嗚噫嗚噫~，主要是寫給兩個可愛的隊友看的，歡迎各位批評指正！ ...
前置知識
①線段樹
②權值線段樹
③桶的思想
④首碼和思想
（以上幾個前置知識我也希望我能有時間寫寫自己的博客講解一下【如果有時間的話嗚噫嗚噫~）
模板題
先上幾道模板題壓壓驚，有從別的博主那裡piao來的，也有自己做到的~
因為深刻感受到了，要學習一個東西，最好還是先看看博客，看看思想，看看代碼實現
然後！拿著你熱乎的手敲模板去A它個幾道模板題考驗一下你的板子，再繼續深刻理解一下這個演算法的精髓，哦~完美！
P5838 [USACO19DEC]Milk Visits G（這道題不算模板，但是還蠻有意思，maybe你模板題都寫過之後可以思考一下這道題，然後敲一敲檢驗一下自己是不是真的會了，這道題是dfs+lca+主席樹的，但是解法不僅限於這一種哦【隊里大佬就有種超級巧妙超級厲害的解法dfs+lca就可以啦，下次有空也打算把題解寫寫博客】）
主席樹的含義
主席樹就是可持久化線段樹，它是一種可持久化的數據結構。
那什麼叫做可持久化的數據結構呢？
可持久化數據結構就是支持歷史詢問的數據結構。
比如一共有54115411次操作，我問你第251251次操作之後這個數據結構長啥樣，你能在約束的時間空間內回答出來就算支持了可持久化，否則就不算。
一種很××的做法就是每次更改構之後我都把它保存下來，然後你問哪次我就去哪次裡面找就是了。但是這顯然在空間上非常不優秀。
然後前輩們發現，每次修改只會讓該數據結構某部分與之前不同，那就只需要記錄這不同的部分就行了。
——引用自淺談主席樹
能解決哪些問題
本質上是為了做 給你一個序列，每次修改後算一個新的版本，詢問某個版本中某個值 這個問題的，但是這個問題衍生開來可以演變出很多問題，比如很經典的主席樹模板題區間第k大問題。
主席樹的原理
普通的線段樹能夠維護當前狀態，而主席樹能夠維護 當前狀態+歷史狀態
我根據身邊老闆的反應以及自己第一次接觸線段樹的感受，猜測應該很多人第一次聽到歷史狀態這個詞都會特別懵逼，那就舉個例子來具體說明吧~
慄子
比如有一個數組，有n個數，分別是a1，a2，...，an，有以下幾種操作：
只要修改一次數組的值就會變成一個新的狀態（第一次更新後為第一個狀態，第二次更新後為第二個狀態，以此類推
①對第 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過的模板題呢~
然後因為我個人是特別懶的，所以直接抓了博主們的圖來用，特此聲明~
