| 😊 | Powered By HeartFireY | Persistent Segment Tree |
| 📕 | 需要的前導知識：線段樹(Segment Tree)、權值線段樹、可持久化資料結構理論(Persistent Data Structure Theory) |
一、可持久化線段樹 簡介
可持久化線段樹，顧名思義，即對線段樹進行可持久化處理之後的線段樹。
在可持久化資料結構的理論中，我們對可持久化的概念有所了解：“可以傳回之前的某個狀态，并在該基礎上進行修改”。可持久化線段樹就是這樣一種結構。
我們從一般思路出發進行分析：想要讓線段樹可持久化，最樸素的方法就是每進行一次操作都建立一顆線段樹。但顯然這是不明智的做法：時間和空間上而言都是非常差的的算法。我們不妨繼續分析一下更新之後與更新之前的結構：每次更新都隻有少量的點被修改。是以大量的點可以繼續使用，無需重建立樹。
本文分兩個部分對可持久化線段樹進行探讨。
值得注意的是：我們一般認為主席樹就是可持久化線段樹，實際上兩者之間有區分：
可持久化線段樹單純指經過可持久化處理之後，能夠查詢、修改曆史節點資料的結構，建立在基礎線段樹的基礎之上；而主席樹建立在權值線段樹的基礎之上，能夠查詢修改曆史節點。二者本質差別在于紀念性可持久化的對象所維護的對象不同(一個維護權值、一個維護值域)。
是以，可持久化線段樹主席樹，準确的說，主席樹可持久化線段樹。
二、可持久化線段樹 基本結構與操作
1.基本結構、建樹操作
首先應該明确一點：由于可持久化結構重疊的特殊性，可持久化線段樹不能采用堆式儲存，是以隻能采取動态開點的方式進行儲存。
不同于後續節點的更新，對于最初的狀态下的線段樹我們采用一次建樹完成：
- 采用遞歸建樹，遞歸函數參數儲存左右邊界(初始化為)、目前元素的指針。同時儲存總計數；
- 遞歸邊界控制為，由于此時左邊界即為指向數組的指針，是以葉子節點指派
- 非葉子節點首先記錄左右子節點的下标，然後遞歸建左右子樹：
- 建立左右節點後非葉子節點 = 左右子節點的和：
根據以上建樹過程，我們以數組為例建立線段樹：
可以看到：不同于基礎線段樹，可持久化線段樹的下标不再遵循堆的規律，這種建樹方式我們稱為動态開點。
結構體封裝版：
#define
#define
#define
#define
struct node{
int val, mark = INT_MIN;
int ls, rs;
}tree[MAXN];
void build(int l = 1, int r = n, int p = 1){
if(l == r) val(p) = a[l];
else{
ls(p) = ++cnt, rs(p) = ++cnt;
int mid = (l + r) >> 1;
build(l, mid, ls(p));
build(mid + 1, r, rs(p));
val(p) = val(ls(p)) + val(rs(p));
}
} 建樹完畢後，上述線段樹已經靜态化，後續的修改操作通過增加新節點來實作。
2.單點修改
假設現在要對加，則操作步驟如下：
首先建立新根結點，更新根節點記錄數組：
建立新節點後對其進行處理。由于我們要修改的元素位于右子樹，是以左子樹部分保持不變，可以繼續使用。是以将原左子樹與新節點相連，同時建立右子節點。
繼續處理，位于目前結點左子樹，右子樹保持不變繼續使用，是以建立左子節點，将原右子節點與新節點相連。
繼續通路左子節點發現到達葉子結點，對原資料進行處理後再逐層回溯，更新路徑上的結點值。
單點修改的操作到此結束。可以看到，對于最初版本的線段樹，其任何資料未被改變。
void update(int x, int d, int p, int q, int cl = 1, int cr = n){
if (cl == cr) val(q) = val(p) + d; // 給葉子節點指派
else{
ls(q) = ls(p), rs(q) = rs(p); // 複制節點
int mid = (cl + cr) / 2;
if (x <= mid) ls(q) = ++cnt, update(x, d, ls(p), ls(q), cl, mid);
// 建立新節點作為左兒子，然後往左遞歸
else rs(q) = ++cnt, update(x, d, rs(p), rs(q), mid + 1, cr);
// 建立新節點作為右兒子，然後往右遞歸
val(q) = val(ls(q)) + val(rs(q)); // 根據子節點給目前節點指派
}
} 3.區間查詢
區間查詢與基礎線段樹幾乎一緻，隻需要額外關注查詢的版本對應的根節點即可。
int query(int l, int r, int p, int cl = 1, int cr = n){
if (cl > r || cr < l) return 0;
else if (cl >= l && cr <= r) return val(p);
else{
int mid = (cl + cr) / 2;
return query(l, r, ls(p), cl, mid) + query(l, r, rs(p), mid + 1, cr);
}
} 4.區間修改
我們需要再次回到标記上進行讨論：
對于标記，我們其實有兩種實作方案：
- 标記上下傳，也就是我們最常用的操作；
- 标記永久化：标記時不用，而是在查詢的時候幹預資料。
二者的一大差別在于，标記上下傳會引發修改結點路徑上的點的更新，而标記永久化不會影響樹上的點。
這點差別是非常有意義的：考慮一棵可持久化線段樹，如果從某節點上傳，則到根節點路徑上的點都會被修改，而可持久化結構導緻了某些結點的複用，這會引發多個版本的線段樹更新，無法指定是哪一版本；同理，下傳标記也會引發不必要的點的更新。是以，我們隻能通過标記永久化對可持久化線段樹進行修改。
于是，我們在查詢時需要額外帶上一個标記：
我們不妨再回顧一下查詢的過程：
我們曾線上段樹的查詢過程中了解到：查詢的過程就是不斷地查詢區間的交集，以此不斷地縮小查找範圍。
如上圖所示，假設查詢到①所示的區間則傳回該節點的值，因為他是待查詢區間的子集；②所示的區間則需要向右遞歸搜尋、③向左遞歸搜尋。
不同于基礎線段樹，可持久化線段樹需要進行額外加永久化标記的操作，即：查詢到待查區間的子集時，傳回(該節點值子集元素個數永久化标記)
同時，遞歸查詢時也要額外對标記進行累加。這點也十分容易了解：
我們思考永久标記的意義：對于目前節點所管轄的區間元素全部加某個值(或者做出某種改變)，是以向下查詢子集時應該帶上目前節點的标記，相當于将标記進行了下放。
ll query(int l, int r, int p, int cl = 1, int cr = n, ll mk = 0){
if (cl > r || cr < l) return 0;
else if (cl >= l && cr <= r) return val(p) + mk * (cr - cl + 1); // 加上帶的标記
else{
int mid = (cl + cr) >> 1;
return query(l, r, ls(p), cl, mid, mk + mark(p)) + query(l, r, rs(p), mid + 1, cr, mk + mark(p)); // 帶着标記傳遞
}
} 對于操作，其基本過程如下：
- 首先對目前節點進行複制；
- 判斷：如果目前節點管轄區間合法，且是待修改區間的子集，那麼對目前新的節點(複制後的節點)的标記執行加操作；
- 如果不滿足條件，則判斷待修改區間是否由左子樹管轄、是否由右子樹管轄，如果是則複制節點，遞歸向左\右建點更新。
值得注意的是，由于缺少傳遞标記，是以由子節點給目前節點指派可能會發生錯誤。
為了得到全包含的區間并計算真實長度，我們隻需要定義區間為即可(保證其為帶查詢區間的子集)。
void update(int l, int r, int d, int p, int q, int cl = 1, int cr = n){
ls(q) = ls(p), rs(q) = rs(p), mark(q) = mark(p); // 複制節點
if (cl >= l && cr <= r && cr > cl) mark(q) += d;
else{
int mid = (cl + cr) >> 1;
if (cl <= r && mid >= l) ls(q) = ++cnt, update(l, r, d, ls(p), ls(q), cl, mid);// 提前進行判斷，以免建立不必要的節點
if (mid + 1 <= r && cr >= l) rs(q) = ++cnt, update(l, r, d, rs(p), rs(q), mid + 1, cr);
}
val(q) = val(p) + (min(cr, r) - max(cl, l) + 1) * d; // 根據需要更新的區間長度計算目前節點的值
} 三、主席樹
差別于一般的可持久化線段樹，主席樹是可持久化權值線段樹。
下面簡單介紹一下主席樹的構造過程：
1.建立空樹
void build(int l = 1, int r = n, int p = 1){
val(p) = 0;
if (l != r){
ls(p) = ++cnt, rs(p) = ++cnt;
int mid = (l + r) / 2;
build(l, mid, ls(p));
build(mid + 1, r, rs(p));
}
} 2.區間離散化
int C[MAXN], L[MAXN], ori[MAXN];
void discretize(int A[], int n){
memcpy(C, A, sizeof(int) * n); // 複制
sort(C, C + n); // 排序
int l = unique(C, C + n) - C; // 去重
for (int i = 0; i < n; ++i){
L[i] = lower_bound(C, C + l, A[i]) - C + 1; // 查找
ori[L[i]] = A[i]; // 儲存離散化後的數對應的原數
} 3.插入離散化資料
for (int i = 0; i < n; i++){
roots[i + 1] = ++cnt;
update(L[i], 1, roots[i], roots[i + 1]);
} 4.查詢區間第大/小
我們已經有了求
[1, r]
内第k大數的方法（查詢相應曆史版本即可），而求
[l, r]
内第k小數，隻需對
kth
函數稍作修改。注意，我們在求
kth
時會用到目前左兒子對應的區間和，現在要排除
[1, l-1]
，那麼把這部分和減去即可。
這一部分的思想與權值樹狀數組很相似。
int kth(int k, int p, int q, int cl = 1, int cr = n){
if (cl == cr) return ori[cl];
int mid = (cl + cr) / 2;
if (val(ls(q)) - val(ls(p)) >= k) return kth(k, ls(p), ls(q), cl, mid); // 往左搜
else return kth(k - (val(ls(q)) - val(ls(p))), rs(p), rs(q), mid + 1, cr); // 往右搜
}