最近正在學習一種資料結構——可持久化線段樹。看了網上的許多部落格，弄了幾道模闆題，思路有點亂了，是以還是來總結整理下吧。
可持久化線段樹
首先要了解此資料結構的基礎——線段樹。百度一下，你就知道！
推薦一下這篇部落格，對線段樹的基本操作講得挺詳細的。
為了更好地理清思路，我在這裡先放個模闆題吧。
洛谷題目傳送門
題目描述
你需要維護這樣的一個長度為\(N\)的數組，支援如下幾種操作
- 在某個曆史版本上修改某一個位置上的值
- 通路某個曆史版本上的某一位置的值
此外，每進行一次操作（對于操作2，即為生成一個完全一樣的版本，不作任何改動），就會生成一個新的版本。版本編号即為目前操作的編号（從1開始編号，版本0表示初始狀态數組）
輸入輸出格式
輸入格式：
輸入的第一行包含兩個正整數\(N,M\)分别表示數組的長度和操作的個數。
第二行包含 N N個整數，依次為初始狀态下數組各位的值（依次為\(a_i， 1 \leq i \leq N\)）。
接下來\(M\)行每行包含3或4個整數，代表兩種操作之一（\(i\)為基于的曆史版本号）：
對于操作1，格式為\(v_i \ 1 \ {loc}_i \ {value}_i v\)，即為在版本\(v_i\)的基礎上，将\(a_{{loc}_i}\)修改為\({value}_i\)
對于操作2，格式為\(v_i \ 2 \ {loc}_i\)，即通路版本\(v_i\)中的\(a_{{loc}_i}\)的值
輸出格式：
輸出包含若幹行，依次為每個操作2的結果。
輸入輸出樣例
輸入樣例#1：
5 10
59 46 14 87 41
0 2 1
0 1 1 14
0 1 1 57
0 1 1 88
4 2 4
0 2 5
0 2 4
4 2 1
2 2 2
1 1 5 91
輸出樣例#1：
59
87
41
88
46
說明
資料規模：
對于30%的資料：\(1 \leq N, M \leq {10}^3\)
對于50%的資料：\(1 \leq N, M \leq {10}^4\)
對于70%的資料：\(1 \leq N, M \leq {10}^5\)
對于100%的資料：\(1 \leq N, M \leq {10}^6, 1 \leq {loc}_i \leq N, 0 \leq v_i < i, -{10}^9 \leq a_i, {value}_i \leq {10}^9\)
經測試，正常常數的可持久化數組可以通過，請各位放心
資料略微兇殘，請注意常數不要過大
另，此題I/O量較大，如果實在TLE請注意I/O優化
詢問生成的版本是指你通路的那個版本的複制
樣例說明：
一共11個版本，編号從0-10，依次為：
0 : 59 46 14 87 41
1 : 59 46 14 87 41
2 : 14 46 14 87 41
3 : 57 46 14 87 41
4 : 88 46 14 87 41
5 : 88 46 14 87 41
6 : 59 46 14 87 41
7 : 59 46 14 87 41
8 : 88 46 14 87 41
9 : 14 46 14 87 41
10 : 59 46 14 87 91
思路分析
很裸的可持久化線段樹闆子題。可持久嘛！就是當出現曆史版本的時候，能夠非常友善地維護一個區間的曆史版本。
自然，我們需要建\(N\)棵線段樹。最粗暴的想法，對每個新版本都把原版本内容複制一遍，然後修改對應的值。這根本不用想，直接MLE+TLE。那維護曆史版本又是怎樣實作的呢？
對于本題，每個版本的序列，我們可以建一棵線段樹來維護它，所有非葉子節點表示的是一段區間，而葉子節點就表示序列的每一個值了。
舉個栗子，樣例中初始版本可以長這樣——
而版本1隻是查詢了一下（線段樹基本操作，這裡不再贅述），然後跟初始版本一模一樣。這就沒必要複制了嘛！我們設版本\(i\)有一個根節點\(root_i\)（表示整段區間），根節點有左右兒子，那麼我們直接讓\(root_1\)的左右兒子指向\(root_0\)的左右兒子就好了，根本不用複制整個線段樹嘛！
那再來看看修改操作。比如從版本1~2。1和0是一樣的，而版本2會長這樣——
有沒有發現1和2真的很像？其實從前到後隻改變了一個節點！那麼其他相同的地方，我們可不可以共用一段記憶體呢？
沒錯，每次建立一個新的版本時，隻要建立\(\log_2 n\)個節點,也就是隻儲存從新版本的根節點到更新的那一個葉子節點的路徑就可以了，不在此路徑上的左/右兒子隻要接原版本對應區間的對應兒子就可以啦。我們可以保證，從對應版本的根節點一定能通路到對應葉子節點的值。
下面是加入新版本的具體實作代碼(我寫的是非遞歸版）：
#define R register int
inline void insert(R*t,R u,R l,R r,R k)
//t是目前節點指針，u是原版本對應t的節點，l、r為目前區間，k為修改點的位置
{
R m;
while(l!=r)
{
*t=++P;//為新節點配置設定空間，P是個外部變量
m=(l+r)>>1;//線段樹操作，計算區間中點
if(k<=m)r=m,rc[*t]=rc[u],t=&lc[*t],u=lc[u];
else l=m+1,lc[*t]=lc[u],t=&rc[*t],u=rc[u];
//上面兩行很關鍵。（if一行）如果k在左子樹中，那麼右子樹沒有變，直接連到舊版本的對應右子樹上，t、u更新為目前左子樹繼續。（else一行反之亦然）
}
in(val[*t=++P]);//讀入新葉子節點的值
}
整個程式的代碼如下
#include<cstdio>
#include<cstring>
#define R register int
const int N=1000009,M=20000009;
int P,rt[N],lc[M],rc[M],val[M];
char I[M<<1],O[M],*fi=I,*fo=O;
bool nega;
inline void in(R&z)
{
while(*fi<'-')++fi;
if(*fi=='-')nega=1,++fi;
z=*fi++&15;
while(*fi>'-')z*=10,z+=*fi++&15;
if(nega)nega=0,z=-z;
}
void oi(R z)
{
if(z>9)oi(z/10);
*fo++=z%10|'0';
}
inline void out(R z)
{
z>0?oi(z):(*fo++='-',oi(-z));*fo++='\n';
}//上面快讀快寫
void build(R&t,R l,R r)//初始化建樹，線段樹基本操作
{
R m;
t=++P;
if(l!=r)
{
m=(l+r)>>1;
build(lc[t],l,m);
build(rc[t],m+1,r);
}
else in(val[P]);
}
inline void insert(R*t,R u,R l,R r,R k)//更新，插入一個新路徑
{
R m;
while(l!=r)
{
*t=++P;
m=(l+r)>>1;
if(k<=m)r=m,rc[*t]=rc[u],t=&lc[*t],u=lc[u];
else l=m+1,lc[*t]=lc[u],t=&rc[*t],u=rc[u];
}
in(val[*t=++P]);
}
inline int ask(R t,R l,R r,R k)//詢問
{
R m;
while(l!=r)
{
m=(l+r)>>1;
if(k<=m)r=m,t=lc[t];
else l=m+1,t=rc[t];
}
return val[t];
}
int main()
{
freopen("ct.in","r",stdin);freopen("ct.out","w",stdout);
fread(I,1,sizeof(I),stdin);
R n,m,i,v,op,loc;
in(n);in(m);
build(rt[0],1,n);
for(i=1;i<=m;++i)
{
in(v);in(op);in(loc);
if(op&1)insert(&rt[i],rt[v],1,n,loc);
else
{
out(ask(rt[v],1,n,loc));
rt[i]=++P;//沒錯，這裡的版本複制其實很簡單
lc[P]=lc[rt[v]];
rc[P]=rc[rt[v]];
}
}
fwrite(O,1,fo-O,stdout);
fclose(stdin);fclose(stdout);
return 0;
}