本系列文章將于2021年整理出版，前驅教材：《演算法競賽入門到進階》 清華大學出版社
網購：京東 當當 ??作者簽名書：點我
有建議請加QQ 群：567554289

??前言：
??可持久化線段樹（Persistent segment tree），或稱為函式式線段樹，中文網上把類似的演算法思路稱為“主席樹”，“主席”并沒有確實的含義，而是詼諧的說法，NOIP選手黃嘉泰說：“這種求 k k k大的方法（函式式線段樹）應該是我最早開始用的”（https://www.zhihu.com/question/31133885/answer/52670974），黃嘉泰的拼音縮寫HJT，正好是古月(H)金帛(J)氵壽(T)的縮寫，所以被網民們稱為“主席”樹，
??函式式編程（Functional programming），與面向物件編程（Object-oriented programming）、程序式編程（Procedural programming）并列，
??以下是正文，

??可持久化線段樹 是基本線段樹的一個簡單擴展，是使用函式式編程思想的線段樹，它的特點是支持詢問歷史版本，并且利用歷史版本之間的共用資料來減少時間和空間消耗，
??可以用影片做比喻來解釋它的思想：
??（1）一秒影片由20幀左右的靜態畫面連續播放而成，每2個相鄰畫面之間差別很小；
??（2）如果用計算機來制作影片，為節省空間，讓每一幀畫面只記錄與前一幀的不同處；
??（3）如何生成完整的每一幀畫面？從第1幀畫面開始播放，后面的每一幀用自己的不同處替換前一幀的相同位置，并填補上相同的畫面，就生成了新的畫面，
??（4）兩幀不同時間的畫面做“減法”，得到一個新的畫面，這個新畫面反映了兩個時間點之間的資訊，
??與影片類似，可持久化線段樹的基本思路是：
??（1）有多棵線段樹（每棵線段樹是一幀畫面）；
??（2）相鄰兩棵線段樹之間差別很小，所以每棵線段樹在物理上只需要存盤與前一棵的不同處，使用的時候再填補并生成一棵完整的線段樹；
??（3）任意兩棵線段樹能“相減”得到一棵新線段樹，它往往包含了題目需要的解，
??可持久化線段樹的基本特點是“多棵線段樹”，根據具體情況，每棵線段樹可以表示不同的含義，例如在“區間第 k k k大問題”中，第 i i i棵樹是區間 [ 1 , i ] [1, i] [1,i]的線段樹；在“hdu 4348區間更新問題”中，第 i i i棵樹是第 t t t時間的狀態，
??需要建多少棵樹？題目給定包含為 n n n個元素的序列，每次用一個新元素建一棵線段樹，共n棵線段樹，
??每棵樹有多少結點？線段樹的葉子結點記錄（或者代表）了元素，如果元素沒有重復，葉子節點就設為 n n n個；如果元素有重復，根據情況，葉子結點可以設為 n n n個（例題hdu 5919），也可以設為不重復元素的數量（例題洛谷P3834），
??可持久化線段樹用到的技術包括：前綴和思想 + 共用點 + 離散化 + 權值線段樹（可以相減） + 動態開點，
??下面用經典問題“區間第 k k k大”來介紹可持久化線段樹的思想，并給出模板，然后介紹幾個典型例題，

1. “區間第k大”問題

主席樹 洛谷 P3834
題目描述：給定n個整數構成的序列a，隊指定的閉區間[L, R]，查詢區間內的第k小值，
輸入：第一行包含2個整數，分別表示序列長度n喝查詢個數m，第二行包含n個整數，第i個整數表示序列的第i個元素ai，下面有m行，每行包含3個整數L，R，k，表示查詢區間[L, R]內的第k小值，
輸出：對每個詢問，輸出一行一個整數表示答案，
資料規模：1 ≤ n, m ≤ 2* 1 0 5 10^5 105, |ai| ≤ 1 0 9 10^9 109, 1 ≤ L ≤ R ≤ n，1 ≤ k ≤ R-L+1

??如果簡單地用暴力法查詢，可以先對區間[L, R]內的元素排序，然后定位到第 k k k小的元素，復雜度 O ( n l o g n ) O(nlogn) O(nlogn)， m m m次查詢的總復雜度是 O ( m n l o g n ) O(mnlogn) O(mnlogn)，
??能否用線段樹求解？線段樹特別適合處理區間問題，例如做區間和、區間最值的修改和查詢，一次操作的復雜度是 O ( l o g n ) O(logn) O(logn)的，在“線段樹”這一節曾指出，這些問題的特征是大區間的解可以從小區間的解合并而來，然而區間第 k k k小這種問題，并不滿足這種特征，無法直接用線段樹，
??本題仍可以用線段樹，但不是在一個線段樹上操作，而是建立很多線段樹，其關鍵是：兩個線段樹相減得到新線段樹，新線段樹對應了新區間的解，
??下面逐步推出可持久化線段樹的解題思路，
??以序列{245, 112, 45322, 98988}為例，序列長度 n n n = 4，
??（1）離散化，把序列離散化為{2, 1, 4, 3}，離散化后的元素值是1 ~ n n n，離散化不影響查找第 k k k小，做離散化操作的原因后文有解釋，如果有重復元素，見后面的解釋，

?? （2）先思考如何用線段樹查詢區間 [ 1 , i ] [1, i] [1,i]的第 k k k小，即查詢的區間是從1個元素到第i個元素，
??對一個確定的 i i i，首先建立一棵包含區間 [ 1 , i ] [1, i] [1,i]內所有元素的線段樹，然后在這棵樹上查詢第 k k k小，復雜度是 O ( l o g n ) O(logn) O(logn)的，
??對每個 i i i，都建立一棵區間 [ 1 , i ] [1, i] [1,i]的線段樹，共 n n n棵樹，查詢每個 [ 1 , i ] [1, i] [1,i]區間的第 k k k小，都是 O ( l o g n ) O(logn) O(logn)的，
??下面的圖，分別是區間[1, 1]、[1, 2]、[1, 3]、[1, 4]的線段樹，為了統一，把4個線段樹都設計成一樣大，即可容納 n n n = 4個元素的線段樹，圓圈內部的數字，表示這個區間內有多少個元素，以及它們在哪些子樹上，把圓圈內的值稱為結點的權值，整棵樹是一棵權值線段樹，

??可以觀察到，每棵樹與上一棵樹只有部分結點不同，就是粗線上的結點，它們是從根到葉子的一條鏈，
??葉子結點的序號實際上就是元素的值，例如葉子[1, 1]表示元素{1}，葉子[2, 2]表示元素{2}，等等，這也是對原序列進行離散化的原因，離散化之后，元素1~ n n n對應了 n n n個葉子，一個結點的左子樹上保存了較小的元素，右子樹上保存較大的元素，
??如何查詢區間[1, i]的第k小？例如查詢區間[1, 3]的第3小，圖(3)是區間[1, 3]的線段樹，先查根結點，等于3，說明區間內有3個數；它的左子結點等于2，右子結點等于1，說明第3小數在右子樹上；最后確定第3小的數是最后一個葉子，即數字4，查詢路徑是[1, 4]->[3, 4]->[4, 4]，
??（3）查詢區間[L, R]的第 k k k小，
?? 如果能得到區間[L, R]的線段樹，就能高效率地查詢出第 k k k小，根據前綴和的思想，區間[L, R]包含的元素等于區間 [ 1 , R ] [1, R] [1,R]減去區間 [ 1 , L ? 1 ] [1, L-1] [1,L?1]，把前綴和思想用于線段樹的減法，線段樹的減法，是在兩棵結構完全的樹上，把所有對應結點的權值相減，線段樹 R R R減去線段樹 L ? 1 L-1 L?1，就得到了區間 [ L , R ] [L, R] [L,R]的線段樹，
??例如區間[2, 4]的線段樹，等于把第4個線段樹與第1個線段樹相減（對應圓圈內的數字相減），得到下圖的線段樹：

??觀察圖中的葉子結點，只有1、3、4這幾個葉子結點有值，正好對應區間[2, 4]的元素{1, 3, 4}，
?? 查詢區間[2, 4]的第 k k k小，方法與前面查詢區間 [ 1 , i ] [1, i] [1,i]的第 k k k小一樣，
?? 時間復雜度分析，2個線段樹相減，如果對每個結點做減法，結點數量是 O ( n ) O(n) O(n)的，復雜度很高，但是實際上只需要對查詢路徑上的結點（以及它們的左右子結點）做減法即可，這些結點只有 O ( l o g n ) O(logn) O(logn)個，所以做一次“線段樹減法 + 查詢第k小”操作，總復雜度是 O ( l o g n ) O(logn) O(logn)的，
?? （4）存盤空間，上述演算法的時間復雜度很好，但是需要的存盤空間非常大，建立n棵線段樹，每棵樹的空間是 O ( n ) O(n) O(n)，共需 O ( n 2 ) O(n^2) O(n2)的空間， n = 1 0 5 n = 10^5 n=105時， n 2 n^2 n2 = 10G，
?? 如何減少存盤空間？觀察這 n n n棵線段樹，相鄰的2棵線段樹，絕大部分結點的值是一樣的，只有與新加入元素有關的那部分不同，這部分是從根結點到葉子結點的一條路徑，路徑上共有 O ( l o g n ) O(logn) O(logn)個結點，只需要存盤這部分結點就夠了， n n n棵線段樹的總空間復雜度減少到 O ( n l o g n ) O(nlogn) O(nlogn)，
?? 下圖演示了建第1棵樹的程序，先建一棵原始空樹，它是一棵完整的線段樹；然后建第1棵樹，第1棵樹只在原始空樹的基礎上修改了圖(1)中的3個結點，那么只新建這3個結點即可，然后讓這3個結點指向原始空樹上其他的子結點，得到圖(2)的一棵樹，這棵樹在邏輯上是完整的，

??建其他樹時，每次也只建與前一棵樹不同的 O ( l o g n ) O(logn) O(logn)個結點，并把新建的結點指向前一棵樹的子結點，從而在邏輯上仍保持為一棵完整的樹，
?? 建樹的結果是：共建立了 n n n棵線段樹，每棵樹在物理上只有 O ( l o g n ) O(logn) O(logn)個結點，但是在邏輯上是一棵完整的線段樹，在這些“殘缺”的線段樹上操作，與在“完整”的線段樹上操作相比，效果是一樣的，
??以上是演算法的基本內容，建樹的時間復雜度是 O ( n l o g n ) O(nlogn) O(nlogn)，m次查詢的時間復雜度是 O ( m l o g n ) O(mlogn) O(mlogn)，
?? 編碼的時候，有3個重要的細節：
?? （1）如何定位每棵線段樹，需要建立 n n n棵線段樹，這 n n n棵線段樹需要方便地定位到，以計算線段樹的減法，可以定義一個 r o o t [ ] root[] root[]陣列， r o o t [ i ] root[i] root[i]記錄第 i i i棵線段樹的根結點編號，
??（2）初始空樹，一般情況下，并不需要真的建一棵初始空樹，而是直接從建第1棵樹開始，因為空樹的結點權值都是0，空樹與其他線段樹做減法是多余的，在沒有初始空樹的情況下，建立的 n n n棵線段樹不僅在物理上都是“殘缺”的，在邏輯上也不一定完整；后面建立的線段樹，形態逐漸變得完整，在“殘缺”的線段樹上做查詢，結果仍然是正確的，因為那些在邏輯上也沒有的結點不需要納入計算，可以看成權值為0，不用寫建初始空樹的代碼，能節省一些編碼時間，
??（3）原始序列中有重復的元素，重復的數字仍需要統計，例如序列{1, 2, 2, 3, 4}，區間[1, 5]的第3小數字是2，不是3，編碼時對n個元素離散化，并用 u n i q u e ( ) unique() unique()去重得到 s i z e size size個不同的數字，每個線段樹的葉子結點有 s i z e size size個，用 u p d a t e ( ) update() update()建新的線段樹時，若遇到重復的元素，累加對應葉子結點的權值以及上層結點的權值即可，用 u p d a t e ( ) update() update()建的線段樹總共仍有 n n n個，不是 s i z e size size個，（有網友說“update函式好像會被杭電掛掉”，可以改個函式名）
??下面的代碼實作了上述演算法，其中新建線段樹的每個結點，是動態開點，其中的查詢函式 q u e r y ( ) query() query()，可以看成在一棵邏輯上完整的線段樹上做查詢操作，

//洛谷P3834代碼, 改寫自：https://www.luogu.com.cn/problem/solution/P3834
#include <bits/stdc++.h>
using namespace std ;

const int MAXN = 200010;
int cnt = 0;        //用cnt標記可以使用的新結點
int a[MAXN], b[MAXN], root[MAXN]; 
                    //a[]是原陣列,b[]是排序后陣列，root[i]記錄第i棵線段樹的根節點編號

struct{             //定義結點
int L, R, sum;  //L左兒子, R右兒子，sum[i]是結點i的權值（即圖中圓圈內的數字）
}tree[MAXN<<5];     //  <<4是乘16倍，不夠用   

int build(int pl, int pr){        //初始化一棵空樹
    int rt = ++ cnt;              //cnt為當前節點編號
    tree[rt].sum = 0;
    int mid=(pl+pr)>>1;
    if (pl < pr){
        tree[rt].L = build(pl, mid);
        tree[rt].R = build(mid+1, pr);
    }
    return rt;  //回傳當前節點的編號
}
int update(int pre, int pl, int pr, int x){   //建一棵只有logn個結點的新線段樹
    int rt = ++cnt;          //新的結點，下面動態開點
    tree[rt].L = tree[pre].L;//該結點的左右兒子初始化為前一棵樹相同位置結點的左右兒子
    tree[rt].R = tree[pre].R; 
    tree[rt].sum = tree[pre].sum + 1;  //插了1個數，在前一棵樹的相同結點加1
    int mid = (pl+pr)>>1;
    if (pl < pr){           //從根結點往下建logn個結點
        if (x <= mid)       //x出現在左子樹，修改左子樹 
            tree[rt].L = update(tree[pre].L, pl, mid, x);
        else                //x出現在右子樹，修改右子樹
            tree[rt].R = update(tree[pre].R, mid+1, pr, x);
    }
    return rt;              //回傳當前分配使用的新結點的編號
}

int query(int u, int v, int pl, int pr, int k){    //查詢區間[u,v]第k小
    if (pl == pr) return pl;  //到達葉子結點，找到第k小，pl是節點編號，答案是b[pl] 
    int x = tree[tree[v].L].sum - tree[tree[u].L].sum;   //線段樹相減
    int mid = (pl+pr)>>1;
    if (x >= k)     //左兒子數字大于等于k時，說明第k小的數字在左子樹
        return query(tree[u].L, tree[v].L, pl, mid, k);
    else            //否則在右子樹找第k-x小的數字 
        return query(tree[u].R, tree[v].R, mid+1, pr, k-x);
}

int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++){
        scanf("%d", &a[i]);
        b[i] = a[i];
    }
    sort(b+1, b+1+n);    //對b排序
    int size = unique(b+1, b+1+n)-b-1; //size等于b陣列中不重復的數字的個數
    //root[0] = buildtree(1, size);   //初始化一棵包含size個元素的空樹，實際上無必要
    for (int i = 1; i <= n; i ++){     //建n棵線段樹
        int x = lower_bound(b+1, b+1+size, a[i]) - b;
                                  //找等于a[i]的b[x]，x是離散化后a[i]對應的值
        root[i] = update(root[i-1], 1, size, x);  
                                  //建第i棵線段樹，root[i]是第i棵線段樹的根結點
    }
    while (m--){
        int x, y, k;
        scanf("%d%d%d", &x, &y, &k);
        int t = query(root[x-1], root[y], 1, size, k); 
                          //第y棵線段樹減第x-1棵線段樹，就是區間[x,y]的線段樹
        printf("%d\n", b[t]);
    }
    return 0;
}

?? 需要分配的空間是 O ( n l o g n ) O(nlogn) O(nlogn)，具體是多少？在線段樹這一節曾指出，一棵線段樹需要分配 4 n 4n 4n個結點，那么總空間約為 n l o g ( 4 n ) nlog(4n) nlog(4n)，題目給定 n = 200000 n = 200000 n=200000， l o g ( 4 n ) ≈ 20 log(4n) ≈ 20 log(4n)≈20，代碼中定義的 t r e e [ M A X N < < 5 ] tree[MAXN<<5] tree[MAXN<<5]夠用，
?? 區間第 k k k大問題的另一種解法是莫隊演算法，見上一節“分塊與莫隊演算法”，

2. 區間內小于等于k的數字有多少

Super Mario hdu 4417
題目描述：給定一個整數序列，有n個數，有m個詢問，詢問區間[L,R]內小于k的整數有多少個，
輸入：第一行是整數T，表示測驗用例個數，對每個測驗，第一行是整數n,m，下一行是n個整數a1, a2, …, an，后面有m行，每行有3個整數L、R、k，
輸出：對每個測驗用例，輸出m行，每行是一個詢問的答案，
資料范圍：1 ≤ n, m ≤ 105, 0 ≤ ai ≤ 1 0 5 10^5 105, 1 ≤ L ≤ R ≤ n，1 ≤ ai, k ≤ 1 0 9 10^9 109

??“區間內小于等于 k k k的數字有多少”問題與“區間第 k k k小”問題很相似，
??（1） u p d a t e ( ) update() update()函式，建 n n n棵線段樹，與例題“洛谷P3834”的代碼一樣，線段樹的每個結點的權值是這棵子樹下葉子結點的權值之和，
??（2） q u e r y ( ) query() query()函式，統計區間 [ L , R ] [L, R] [L,R]內小于等于 k k k的數字有多少個，首先用線段樹減法（線段樹 R R R減去線段樹 L ? 1 L-1 L?1）得到區間 [ L , R ] [L, R] [L,R]的線段樹，然后統計這棵樹上比 k k k小的數字即可，統計方法就是標準的線段樹“區間和”查詢，例如圖2，它是{1, 3, 4}的線段樹，如果求小于等于 k k k=3的數字有多少，答案就是求這棵線段樹的區間[1, 3]的區間和，它等于[1, 2]區間和加上[3, 3]區間和，同樣，這里做線段樹的減法，并不需要把每個結點相減，只需要對查詢路徑上的結點做減法（即結點[3, 3]和結點[1, 2]），只涉及到 O ( l o g n ) O(logn) O(logn)個結點，

3. 區間內有多少不同的數字

Sequence II hdu 5919
題目描述：一個整數序列，有n個數A[1], A[2], …, A[n]，做m次詢問，第i個詢問，給定兩個整數Li、Ri，表示一個區間，區間內是一個子序列，其中不同的整數有ki個，輸出第ki/2個整數在這個子序列中第一次出現的位置，
輸入：第一行是整數T，表示測驗用例個數，對每個測驗，第一行是2個整數n和m，下面一行是n個整數，表示序列，后面m行，每行有兩個整數Li、Ri，
輸出：對每個測驗，輸出一行，包括m個回答，
資料范圍：1 ≤ n, m ≤ 2* 1 0 5 10^5 105, 0 ≤ A[i] ≤ 1 0 5 10^5 105

?? 首先求區間內有多少個不同的數字，若按前面建主席樹的方法，第 i i i棵主席樹記錄區間 [ 1 , i ] [1, i] [1,i]內的數字情況，如何定義葉子結點的權值？考慮2種方案：
??（1）葉子結點的權值是這個數字出現的次數，那么查詢區間 [ L , R ] [L, R] [L,R]內不同數字個數時，用線段樹 R R R減去線段樹 L ? 1 L-1 L?1，得到區間 [ L , R ] [L,R] [L,R]的線段樹，此時每個葉子結點的權值是這個數字在區間內 [ L , R ] [L,R] [L,R]出現的次數，在這棵線段樹上，無法以 O ( l o g n ) O(logn) O(logn)的復雜度計算不同的數字個數，
??（2）葉子結點的權值等于1，表示這個數字在區間 [ 1 , i ] [1, i] [1,i]出現過；等于0，表示沒有出現過，這樣做可以去重，但是無法用線段樹減法來計算區間的不同數字個數，例如，區間 [ 1 , L ? 1 ] [1, L-1] [1,L?1]內出現某個數字，區間 [ L , R ] [L, R] [L,R]內再次出現這個數字，它們對應的葉子結點權值都是1；對線段樹 R R R和 L ? 1 L-1 L?1做減法后，得到 [ L , R ] [L, R] [L,R]區間的線段樹，這個葉子結點的權值是0，表示這個數字不存在，而區間 [ L , R ] [L, R] [L,R]內其實是有這個數字的，
??這題仍可以用主席樹，但是需要使用新的技巧：倒序建立這 n n n棵線段樹，
??（1）每棵線段樹的葉子結點有 n n n個，這與例題“洛谷P3834”的線段樹不同，第 i i i個葉子結點記錄第 i i i個元素是否出現，
??（2）按倒序建立線段樹，一個元素建立一棵線段樹，用第 n n n個元素 A [ n ] A[n] A[n]建立第1個線段樹，用第 n ? 1 n-1 n?1個元素 A [ n ? 1 ] A[n-1] A[n?1]建立第2個線段樹…，共有 n n n棵線段樹，用元素 A [ n ] A[n] A[n]建立第1棵線段樹時，第n個葉子結點的權值是1；…；建立第 i ? 1 i-1 i?1棵線段樹時，若 A [ i ? 1 ] A[i-1] A[i?1]在區間 [ i , n ] [i, n] [i,n]中曾出現過，將第 i i i個葉子結點的權值置為0，然后把第 i ? 1 i-1 i?1個葉子結點權值記為1，這個操作把重復的元素從第 i ? 1 i-1 i?1個線段樹中剔除，只在第1次出現的葉子結點位置記錄權值，如何編程實作？可以定義 m p [ ] mp[] mp[]陣列， m p [ A [ i ] ] = i mp[A[i]] = i mp[A[i]]=i，表示元素 A [ i ] A[i] A[i]在第i個線段樹的第 i i i個葉子結點出現；建第 k k k個線段樹時，若 m p [ A [ k ] ] > 0 mp[A[k]] > 0 mp[A[k]]>0，說明 A [ k ] A[k] A[k]這個元素曾出現過，先把第 k k k個線段樹的第 m p [ A [ k ] ] mp[A[k]] mp[A[k]]個葉子結點權值置為0，然后把第 k k k個葉子結點權值置為1，
??（3）查詢區間 [ L , R ] [L, R] [L,R]內不同數字個數，第 L L L棵線段樹，只記錄了 A [ L ] A[L] A[L] ~ A [ n ] A[n] A[n]區間內不同數字的情況，而不包括 A [ 1 ] A[1] A[1] ~ A [ L ? 1 ] A[L-1] A[L?1]，那么只需要在第 L L L棵線段樹上，按標準的區間查詢操作計算 [ 1 , R ] [1, R] [1,R]的區間和，就是答案，
??題目要求輸出區間[ L , R ] L, R] L,R]內第 k / 2 k/2 k/2個整數在這個區間中第一次出現的位置，由于第 L L L棵線段樹記錄的就是 A [ L ] A[L] A[L] ~ A [ n A[n A[n]第1次出現的位置，那么只需要在這棵線段樹上查詢 [ 1 , R ] [1, R] [1,R]的第 k / 2 k/2 k/2個葉子結點即可，

4. 區間更新

To the moon hdu 4348 區間更新
題目描述：給定n個整數A[1], A[2], …, A[n]，執行m個操作，有以下幾種操作：

1. C L R d 區間[L, R]每個A[i]加上d，時間 t t t加1，注意只有這個操作才會改變 t t t，第1個操作 t t t=1，
2. Q L R 查詢區間和
3. H L R t 查詢時間t的歷史區間和
4. B t 回傳時間t，t以后的操作全部清空
   1 ≤ n, m ≤ 105, |A[i]| ≤ 1 0 9 10^9 109, 1 ≤ L ≤ R ≤ n，|d|≤ 1 0 4 10^4 104

??若沒有時間 t t t，只需要建一棵線段樹，就是標準的線段樹模板題，加上時間點 t t t后，每個時間點建一棵線段樹，這正符合主席樹的標準應用，按標準的主席樹編碼即可，

習題

??區間第k大：hdu2665
??可持久化陣列：洛谷 P3919
??主席樹專題訓練：https://www.cnblogs.com/HDUjackyan/p/9069311.html
??帶修改的主席樹：ZOJ 2112 Dynamic Rankings