可持久化資料結構 理論

一、可持久化資料結構簡介

可持久化資料結構(Persistent data structure)總是可以保留每一個曆史版本，并且支援操作的不可改變性(immutable)。

二、可持久化分類

1.部分可持久化 (Partially Persistent)

所有的版本均可通路，但是隻有最新版本可以修改

2.完全可持久化 (Fully Persistent)

所有版本均可即通路又修改。

若支援将兩個曆史版本合并，則又稱為彙合可持久化 (Confluently Persistent)。

三、實際應用

1.幾何計算

在幾何計算中有許多離線算法，例如懸線掃描法，其基本政策是一次掃描後給出所有詢問的回答，在時間複雜度分析相當優秀。但在強迫線上的情況下，每次都要進行一次懸線掃描，詢問操作的時間複雜度就從對數時間降為線性。

為了解決時間複雜度上的問題，在這裡可以引入可持久化的思維。我們将掃描線的時間軸作為一個變動依據，持久化相關的結構，隻要我們能将詢問在對數時間内穿梭于這個時間軸，必能動态解決先前的問題。

2.字串處理

為了達到非常高效率的合并操作，防止大量重複性字串的生成伴随的效能退化，使得各方面的操作都能遠低于線性操作。如C++中的rope就是一個可持久化的資料結構。不隻是字串操作。若處理類型有大量重複操作，均可以考慮将資料結構進行可持久化處理，以達到壓縮時間開支的效果。

3.版本回溯

實際上就是對應大部分的應用軟體中的redo/undo。如果資料庫/操作變動為了高效率操作而會配上複雜的結構（并不像 hash, set 反轉操作隻需要常數或對數時間），那麼為了快速回推變動結果，持久化結構就是要減少 redo/undo 的花費。

資料庫本身可以常數回推，紀錄變動的部分情況即可。而應用層的計算，大部分實作都是砍掉快取，并且重新計算出一份新的結構，有時候回推的變動大小為 m，為了重新計算結構而消耗了 ，如果 和

4.函數式程式設計

四、幾種常見的可持久化資料結構

1.可持久化線段樹

2.可持久化塊狀數組

3.可持久化平衡樹

4.可持久化字典樹

5.可持久化可并堆