contents
回顧
幾年前，跟 liouzhou101 一起搞了很多記憶中系列題目，有一題與陣列很相似，但操作更複雜一些。陣列的操作只有下列幾種
get(index): 回傳索引為 index 的元素，其中 $\text{index} \in \left [0, n-1 \right ]$set(index, value): 修改 index 上的元素pushBack(value): 陣列尾端後接一個新的元素popBack(): 移除陣列尾端的最後一個元素
從演算法課程中，我們學到 C++ 中的 std::vector 可以做到均攤 $\mathcal{O}(1)$，其大致的做法為陣列快填滿容量時，倍增其大小後轉移原先的所有元素到新的容器上，均攤計算為每次增加的元素都需要預先支付未來轉移自己、轉移對應的另一個元素、移除自己、移除對應的另一個元素的花費，因此均攤花費為常數。
而這樣子的均攤操作在可持久化卻是不利的，因為單一操作的最慘複雜度為 $\mathcal{O}(n)$，意味著可能在同一個操作上，使用 $m$ 次持久化會造成時間複雜度退化成 $\mathcal{O}(mn)$。因此，我們需要最小化最慘時間複雜度的結構。
當年初學者的我，切入觀點有二元樹 (binary tree)、塊狀表 (unrolled linked list)，前者讓操作必為 $\mathcal{\Theta}(\log n)$、後者為 $\mathcal{\Theta}(\sqrt{n})$，從理論分析上一定優先選擇前者實作，但如果操作有特別的比例問題，如 get(index)、pushBack() … 等，這時候快取能力好的塊狀表反而有優勢，二元樹因指標的使用導致整體的內存使用率不高，透過 2-3 tree 那一種將節點儲存多個元素的設計，就相當於把塊狀表拉成樹狀，其效果也不錯，但在計算上會更需要耗費工夫。
塊狀表 (Unrolled Linked List)
任何操作皆為 $\mathcal{\Theta}(\sqrt{n})$，修改操作皆需要複製整個節點。在可持久化情況時，預先每一個塊的大小較為不可行，故做不到動態調整塊狀大小。
二元樹 (Binary Tree)
利用二元樹建立可持久化的情況有很多種編碼，以及紀錄節點的優化方式，這將會影響到我們的效率。盡可能地不在節點中儲存欄位 size 即可達到索引。若二元樹節點定義為
|
|
葉與內部節點皆帶有元素值，那麼在陣列的新增刪除尾端的操作，我們可以透過類似 heap 的方式，將其設計成不用旋轉操作、不用紀錄樹大小的編碼。當節點編碼為 $k$，則兩個子節點 $2k$ 和 $2k+1$，實作時只需要紀錄整體大小，接著在走訪過程中，採用位元運算得到其子樹大小作為操作依據。
|
|
這樣的編碼問題，對於陣列實作時，發現 push/set(index, value) 時，時間複雜度為 $\mathcal{\Theta}(\log \text{index})$，那動態將 $n$ 個元素推入的時間必為 $\mathcal{\Theta}(n \log n)$，靜態建造則為 $\mathcal{\Theta}(n)$。索引值越大的元素，其操作花費越高。
設計函數庫時，我們通常希望盡可能地讓複雜度對稱，也就是兩端的索引速度不會差太多，即使是亂數也好，因為演算法設計、真實生活中的應用大多都會偏向一方，很可能總是觸發最慘情況。
Braun Tree
另一種編碼設計，對於每一個節點皆滿足右子樹大小最多比左子樹大小多一個，由於每一個節點都滿足，按照插入順序，可以得到下圖
|
|
明顯地，如同霍夫曼編碼一樣，這一個 1-indexed 的情況，最低位 0 則往左子樹、反之為右子樹。每一個操作皆為對稱的，但複雜度如同一般的二元搜尋樹，作為陣列操作也不滿足期待。
若用於可持久化陣列的基底，代碼量非常少，遞迴定義使得操作簡單，我們甚至可以連整體大小都不用儲存，透過其遞迴定義可在 $\mathcal{O}(\log^2 n)$ 得到，但大部分陣列使用都是會希望 A.size() 是可以在 $\mathcal{O}(1)$ 完成的。這樣的設計在優先隊列 (priority queue) 更友善，因為鮮少需要去拿到 size，只需要回傳這個優先隊列是否為空。
同樣地，這依舊不是實作可持久化陣列的首選。
線段樹 (Segment Tree)
線段樹的設計有一個缺點，大部分的情況總是預先知道大小，然後再代入修改操作。
如果要做到動態的增加大小，則採用 top-down 的展開節點方法。如根節點一開始設計範圍為 $\left [0, 2^{32} \right ]$，當我們 push 一個新的元素至尾端時，相當於開出一個葉節點為 index = size，同理 pop 操作。一開始預設最大上限 $M$，單一操作的時間複雜度必為 $\mathcal{\Theta}(\log M)$。
以上述的狀況，每一次操作複雜度必為 $32$，作為函數庫的設計而言，這樣的寫法沒有彈性，而且要是未來超出指定大小，修改就非常的緩慢，更因為在持久化的環境下，不可能在對數時間內轉移其架構。
Leftist Leaf Tree
其概念類似二項堆積 (binomial heap)，我們將使用 $\log n$ 棵樹表示整個序列。將內容放置於葉節點上，並且每一個樹皆為完美樹，無須額外紀錄子樹大小。
例如：當 n = dec(11) = bin(1011) 時，用三棵大小分別為 8, 2, 1 的樹表示之。當 push 一個新的元素至尾端時，與最右邊的子樹 1 合併成大小為 2 的樹，再與左邊的子樹合併成大小為 4 的子樹，最後成為 n' = dec(12) = bin(1100)，用兩棵子樹表示之。同理 pop 操作，模擬二進制的退位。
每一個操作皆為 $\mathcal{O}(\log n)$，且分布較為一般的二元樹均勻。並解決一開始我們在二元樹上遇到的問題，動態將 $n$ 個元素推入的時間，整體複雜度為 $\mathcal{\Theta}(n)$。因此，這是目前實作可持久化隊列的首選。
其他
函數式理論複雜度最好的結構為 finger tree，實作複雜度相當高，卻具備了合併兩個陣列的特殊操作，這是以上結構皆不具有操作。實際的效能無法預測，通常常數過大而無法使用。有朝一日，我們再來挑戰這偉大的結構吧。