後綴陣列把一段文字的「所有結尾片段」排好序,之後要在這段文字裡快速搜尋、找最長重複片段都很方便(搜尋引擎、DNA 序列比對常用)。 持久化線段樹則是「會保留每個歷史版本」的資料結構——每次修改不覆蓋舊資料,而是只新增少少幾個節點、其餘和舊版本共用, 所以能隨時查任何一個過去版本(用途:版本控制的撤銷/重做、以及「求某區間第 k 小的數」這類經典問題)。
在一大段文字裡想快速找出某個詞出現在哪、或哪一段重複最多次，一個字一個字比對太慢；而想反悔剛才的修改、 回到幾步前的樣子，把整份資料整包複製存檔又太佔空間。這頁的兩個結構正好各解一題：後綴陣列先把文字裡 所有結尾片段排好序，像書末的索引一樣，讓你用二分搜尋快速定位任何字；持久化線段樹則像文件的版本紀錄， 每次只多存被改到的那幾個節點、其餘和舊版共用，所以每個過去版本都留得住、又不佔空間。下面你會看到它們各自怎麼運作。
兩者都是「先把資料整理好、再用結構省下重複工作」的代表：後綴陣列把一段文字的所有後綴排序成表， 搭配 LCP（最長共同前綴）陣列與二分搜尋，把模式字串搜尋壓到 O(m log n)；持久化線段樹則是一般線段樹的 「路徑複製」延伸——每次更新不覆蓋舊資料，而是沿更新路徑新建 O(log n) 個節點、其餘子樹與舊版本直接共享 參照，換取「所有歷史版本皆可查詢」且空間增量只有 O(log n)。
倍增法（doubling）：初始 rank[i]=首字元碼、sa[i]=i，每輪 k=1,2,4,... 依 (rank[i], rank[i+k]) 二元組重新排序 並指派新名次，二元組全相異即提前結束（本頁 complexity 依 Java 建構法誠實標 O(n log²n)）。排序完成後， Kasai 演算法依原始位置序、利用 h 只減不歸零的攤提技巧，以 O(n) 求出每個排名的 LCP（與前一名後綴的最長共同前綴）。 最後對固定 pattern 做兩次二分搜尋：先找「第一個 >= pattern」的下界，再找「第一個 > pattern」的上界， [下界,上界) 區間內即所有匹配位置。
update(version, index, value) 從指定版本的根出發，沿更新路徑複製節點（newNode = node.copy()）： index <= mid 複製並遞迴左子、否則複製並遞迴右子，另一側子樹不修改，直接共享舊節點參照（不複製）； 抵達葉節點直接賦新值，回溯時重算 sum，新版本的根收進 versions[]。query(version, l, r) 則從該版本的根 出發做標準線段樹查詢：完全包含回傳 sum、完全不相交回傳 0、部分重疊遞迴左右子相加。