版本控制不是 Git 的專利。線段樹也能做到「改一個值，舊的那版還在」——而且省到讓人意外。
為什麼需要它？線段樹不是已經很強了嗎？
一般線段樹強在當下：區間和、區間最值，改一個值 O(log n)、查一段 O(log n)，沒話說。但它有個致命的健忘症——你一改值，上一版就永遠消失了。
問題是有整類題目要問的正是歷史：「陣列在第 5 次操作後、[3, 8] 這段的和是多少？」或者更經典的「區間 [L, R] 裡第 k 小的數是誰？」這些都需要你手上同時握著很多個版本的線段樹，隨時能翻回任何一版去查。
最直覺的作法是每改一次就把整棵樹拷貝一份。撞牆撞得很快：一棵 n 個葉子的線段樹有 ~2n 個節點，你做 m 次修改就是 O(nm) 空間。n 跟 m 都上到 10^5，這數字直接爆掉記憶體。
持久化線段樹的招數，是看穿一件事：改一個位置，其實只動到從根到那個葉子的一條路徑，深度 log n。 樹上其他絕大多數節點根本沒變——那幹嘛複製它們？
路徑複製：只複製被改到的那條路
核心技巧就一句話：每次更新，只新建「從根到修改點」這條路徑上的節點，路徑以外的子樹，新版本直接指回舊版本的節點共享。
版本 0（原始）：
[0,7]
/ \
[0,3] [4,7]
/ \
[0,1] [2,3]
更新位置 2 → 產生版本 1：
root1 root0（原封不動，仍可查）
| |
[0,7]' [0,7]
/ \ / \
[0,3]' \ ─────共享────► [4,7] ← [4,7] 沒被動到，兩版共指同一節點
/ \
[0,1] [2,3]'
▲
└── 共享舊版的 [0,1]
打了 ' 的 = 這次新建的節點（[0,7]'、[0,3]'、[2,3]'）
數量 = 這條 root→修改點路徑上的節點數，約 log n看懂這張圖，整個資料結構就懂一半了。root1 是一棵看起來完整的線段樹，但它 90% 的節點是跟 root0 借的。新建的只有那條通往位置 2 的路徑。舊的 root0 一根汗毛都沒少，你之後拿它查任何區間，結果跟修改前完全一樣。
每個版本就存一個根節點，要哪一版就從哪個根走下去：
// 每個版本保留一個根節點
List<Node> roots = new ArrayList<>();
roots.add(build(0, n - 1)); // 版本 0：初始建構
// 更新 → 不覆蓋舊版，而是長出一個新版本
void update(int version, int pos, long delta) {
Node newRoot = update(roots.get(version), pos, delta);
roots.add(newRoot); // 新根接在版本清單尾巴
}真正的巧勁全在遞迴這一段——進到節點先複製自己，然後只對「有走到」的那一側遞迴，另一側原地共享：
Node update(Node node, int pos, long delta) {
Node newNode = node.copy(); // 先複製當前節點（連兩個子指標一起拷）
if (node.left == node.right) { // 到葉子了
newNode.sum += delta;
return newNode;
}
int mid = (node.left + node.right) / 2;
if (pos <= mid)
newNode.leftChild = update(node.leftChild, pos, delta); // 只有左側重建
// newNode.rightChild 還指著舊節點 —— 這就是「共享」
else
newNode.rightChild = update(node.rightChild, pos, delta); // 只有右側重建
newNode.sum = newNode.leftChild.sum + newNode.rightChild.sum;
return newNode;
}node.copy() 那行同時拷貝了左右兩個子指標——關鍵在於只有被遞迴的那一側會被覆寫成新節點，另一側就這樣繼續指向舊版。這就是共享的全部祕密，沒有魔法。
查詢反而是最無聊的部分：跟一般線段樹一模一樣，只是入口從「the 那棵樹」換成「你指定版本的根」：
long query(int version, int L, int R) {
return query(roots.get(version), L, R); // 從第 version 版的根往下查
}主席樹：區間第 k 小的標準答案
持久化線段樹最漂亮的應用，是解「靜態區間第 k 小」——這在中文競程圈幾乎跟「主席樹」畫上等號。
想法是對前綴各建一個版本。線段樹這次不存區間和，而是當值域上的計數桶：把每個數字丟進它所屬值域的葉子，記「這個值出現幾次」。
對前綴逐個插入，留下每一版：
roots[0] = 空樹（什麼都還沒插）
roots[1] = 插入 arr[0] 後
roots[2] = 插入 arr[0], arr[1] 後
...
roots[i] = 前 i 個元素的值域計數樹
關鍵觀察：roots[R] 減掉 roots[L-1]，
逐節點相減，得到的正好是「只含 arr[L..R] 這段元素」的計數樹。
在這棵差分樹上找第 k 小：
看左子樹（較小值域那半）裡裝了 cnt 個元素——
cnt >= k → 第 k 小落在左半，往左走
cnt < k → 往右走，並把 k 扣掉 cnt（前 cnt 名不算了）
一路走到葉子，那個值域就是答案妙就妙在「兩棵版本相減」這步。因為 roots[R] 和 roots[L-1] 大量共享節點，相減時同一結構位置的兩個節點一起往下走，計數 = 右版該節點 - 左版該節點，就把 [L, R] 這段的貢獻乾淨地剝出來了。整趟查詢只沿著一條 log n 的路徑走，不用真的把差分樹建出來。
沒有持久化，這題你得對每個區間重算，或搬出更重的離線做法；有了它，前綴版本一次建好，之後每次查詢 O(log n) 就吐答案。這就是為什麼它是這題的標準解，不是「其中一種解」。
複雜度：省在哪，一張表說完
| 操作 | 時間 | 空間 |
|---|---|---|
| 初始建構 | O(n) | O(n) |
| 更新一次（長一個新版本） | O(log n) | O(log n) |
| 查詢任意版本 | O(log n) | — |
| m 次更新後總空間 | — | O(n + m log n) |
重點就是那個粗體的 O(log n)。跟「每次整棵複製」的 O(n) 擺在一起看，差距是 log n 對 n——n 上到十萬，就是「多幾十個節點」跟「多二十萬個節點」的差別。持久化不是把版本控制變可能，是把它從奢侈品變成能上場的日常工具。
🎬 互動視覺化：持久化線段樹動畫 — 一步步看更新時哪條路徑被複製、哪些節點跟舊版牽著同一條線共享，比盯著上面那幾張 ASCII 圖腦補快得多。
一般線段樹活在當下，改了就忘；持久化線段樹記得每一個昨天，而且記得很省——只把改過的那一頁抄下來，其餘的翻回舊本子接著看。
接下來往哪走
- Segment Tree 線段樹 — 前置知識：先把「當下版本」的線段樹搞熟，再談怎麼留住歷史
- Suffix Array 後綴陣列 — 同一個互動視覺化頁的鄰居，另一個把「預處理換查詢速度」玩到極致的結構