用一個陣列實作的動態排序容器

去年出 ICPC 2021 台北站 的 題目 (codeforces)，在驗題時想了一個資料結構。

這個資料結構是動態排序的容器，是用一個 array 實作的。它的時間複雜度比常見的 balanced binary search tree 要差一點，不過它把所有的資料緊密地排在連續的記憶體，不需要額外的指標，memory locality 比較好。並且如果需要使用 gdb 的時候，直接用眼睛看這一串連續的記憶體就可以知道有沒有問題，不用 trace 指標。

以下是這個容器各操作的時間複雜度 (假設容器內容物的數量為 N)：

• insert 的時間複雜度是 amortized O(lgN)，單次的 worst case 是 O(N)
• query 一個 value 是否存在、或是不存在時輸出前後最相近項的時間複雜度是 O(lg^2N)
• query 一個 value 在這容器裡排序第幾大的時間複雜度也是 O(lg^2N) (這個是 red-black tree 不能作的操作，不過 size-balanced tree 可以)
• delete 一個指定 value 的元素是 O(lg^2N)

實作

靜態結構

從最左邊開始，湊滿盡量大的 2 的冪次為一段，剩餘的部分也是盡量湊滿 2 的冪次為一段，一直切到吃光整個 array。這樣把整個 array 切成若干小段，每一個小段裡分別都是排序好的元素。這樣的小段，最多會有 O(lgN) 個。

以下是容器裡存了 7 個元素的例子：

以長度 7 為例就是拆成 3 個小段：4個、2個、1個。

query

query 一個 value 是否存在的方法，或如果不存在的時候要找最相近的一個出來，就是在這每一個小段裡分別作一次 binary search。所以花的總時間 worst case 是 O(lg\frac{N}{2} + lg\frac{N}{4} + ... + lg1) = O(lg^2N)

query 一個 value 在這容器資料裡可以排第幾大，也是在每一個小段作 binary search，就可以找出在每一個小段裡，比這個 value 小的元素有幾個，把它們通通加起來就是整個容器裡比 value 小的元素有幾個，那就是 value 在這容器的排名。花的時間和上面是一樣的。

insert

新增一個 value 進去的時候，先把它放在 array 的末端。接下來看它會補滿多少層 2 的乘冪，每一層作一次 merge sort 的 merge。 前面舉例長度 7 的容器如果 insert 一個 5，就會是下面這樣的過程：

worst case 會作 O(lgN) 次 merge，不過 merge 的長度是 2、4、8、16… 這全部加起來最多是 2N，所以單次 insert 的 worst case 是 O(N)。

而若考慮所有的 insert 的總耗時，分開考慮 merge 操作時的小段長度：每 insert 2 次會作到一次長度 2 的小段 merge；每 insert 4 次會作到一個長度 4 的小段 merge；依此類推。 在 insert N 次之後會作 N 次長度 1 的小段 merge、\frac{N}{2} 次長度 2 的小段 merge、\frac{N}{4} 次長度 4 的小段 merge、…，每一種長度的 merge 都剛好用掉 O(N) 的時間。而總共會有 lgN 種長度，所以總耗時是 O(NlgN)，單次平均耗時是 O(lgN)，也就是 amortized O(lgN)。

merge 的時候，最多會額外使用 \frac{N}{2} 格記憶體 (先把左小段複製到額外的記憶體，然後從左小段開始填入右小段與額外記憶體的 merge)。如果預期這個容器會持續長大，可以考慮讓額外的記憶體就是整個容器最右邊的延伸，爾後就漸漸成為存放新元素的空間不需要歸還了。如果想節省掉額外的記憶體，可以考慮換成時間複雜度多乘一個 O(lgN) 的 quick sort 或 heap sort、或找其他宣稱 inplace merge sort 的方法來代替，作為空間成本與時間成本之間的取捨。

delete

如果不需要 delete 的話，上述的資料結構實作起來非常簡單，加進 delete 之後就會複雜不少，而使用情境倒是常有不需要 delete 的時候。

delete 的實作，原則就是先標註要刪除的元素留著一個洞，等之後 merge 的範圍含括到它的時候再把這個洞移到 merge 範圍的最右邊 (就是整個 array 的最右邊) 並縮短容器的大小。如果 merge 時在某一層發生了移洞縮短，那麼這一輪就一定不會再往更上一層 merge。這個原則還算單純。

不過如果只是把要刪除的位置標註起來，而不巧遇到的操作順序會造成好多個洞連續排在一起沒有被 merge 清除，更不巧的是 query 最相近元素時 value 剛好落在這一串連續洞的範圍裡，那麼要去找到最接近的元素也就是連續洞的邊緣，就有可能會花到 O(N) 的時間。所以需要額外作一些註記，以便 query 落在連續洞的時候，可以很快知道岸邊在哪裡，並且這個註記的動作也不能太花時間，像是如果要在連續洞裡每個位置都去更新邊緣的距離會花到 O(N) 的時間也不可以。這個額外的註記方法會有一點複雜。

由於每一個小段的長度都是 2 的乘冪，所以 binary search 時會讀取的位置順序是固定的，依讀取的順序可以把每個小段分別看成一個結構固定的 binary search tree。既然是 tree，就可以在 subtree 的 root 註記整個 subtree 的共用資訊。然後我們再利用類似 tree node delete 的手法，讓「洞」優先出現在 leave 的位置。也就是如果想刪除的是一個還有 children 的 internal node，那麼就去找一個 leave (left subtree 的 right-most leave 或 right subtree 的 left-most leave，如果找到的 right-most/left-most 的另一側還有 children 的話，再從這個 subtree 裡找出 right-most/left-most 來取代自己) 搬家覆蓋掉原本要刪除的 internal node，然後把「洞」放在被搬走的 leave 的位置。這樣子，選定好「洞」的位置的時候，這個位置以下的整個 subtree 都是已經被清空了的。所以當我們標註一個元素是已刪除的洞，那就表示這個元素的位置以下整個 subtree 都是空的。這個過程和一般的 binary tree delete 一樣，是 O(height) = O(lgN) 步可以完成，也就是成功 delete 一個元素最多增加 O(lgN) 步，合算一開始 query 出這個待刪元素的 O(lg^2N) 總耗時還是 O(lg^2N)。

query 的時候如果遇到被清空的 subtree，就返回它的 ancestor 由下往上層層找非空的 left sibling 或 right sibling (看是要找比 value 小的最近值或比 value 大的最近值) 裡的 right-most 元素 (right sibling 找 left-most 元素)。找 left-most / right-most 的時候，先看想要的方向的 subtree 如果非空，就往那個 subtree 走，不然另一個 subtree 一定是非空的 (不然它們的 parent 應該會標註整個 subtree 都是空的)，那就往這個非空的 subtree fallback。這個走訪的步驟一共是 binary search 碰到清空的 subtree 是 O(lgN) 步，往回爬 ancestor 找非空的 sibling subtree 要 O(lgN) 步，爬 left/right-most leave 也是 O(lgN) 步。query 的時間複雜度和沒有 delete 功能的時候一樣。

delete 實際實作起來，還有一些細節要處理，沒有像上面描述的抽象概念這麼順利。query 的 binary search 方式，如果想讓平均比較次數少一點，query 輸入的 value 只會和 array 裡的元素比較一次，就會決定要往左或往右找，例如說 value < 元素i，搜尋範圍就改為 [0, i-1)；否則搜尋範圍改為 [i, N)，也就是不會多作一次比較來確認 元素i 是不是剛好就是輸入的 value。這樣的搜尋方式所對應的 binary search tree，其搜尋結果一定不會停在 internal node，一定都會走到 leave node 為止，而 internal node 的 value 就是 right subtree 的 left-most leave node value。以前面 insert 5 之後的例子來看，只作一次小於比較的 binary search tree 是這樣：

1 放在最左上當 root 的意思，是因為我們對路徑上每一個 node 都只作一次小於比較，所以最開始我們需要先確定要尋找的 value 不會比整個容器所有的東西還小。最下面虛線部分是 tree 的 leave，也就是 query 的終點。但它們其實都是曾經經過的 internal node，如果直接在這些位置標記刪除留洞的話，等於是把對應的 internal node 以下整個 subtree 都砍掉了。所以選出要刪除的 leave 之後，要從它們對應的 internal node 出發，找出替代的 children leave，並且要避免選到自己 (也就是 right subtree 的 left-most leave)。

這樣留洞的標記方式，每個位置只需要一個 value，比一個 bit 還少。就是如果各元素的值域有任何一個不會用到的值，就可以拿它來表示這個位置是洞，不需要額外的空間。而如果元素的值域所有的值都會使用到的話，那可能還是需要耗用一個 bit 來標記。如果使用了值域裡用不到的值來標記洞，query 和 insert merge 的時候，大小的比較要記得對這個標記用的值作特殊處理，它不能參與正常的大小比較。

這一個標記方式可以維持 query 最近值的效率，但是要找出 value 是第幾大就不夠用了，因為我們需要知道 query 到 leave 的路徑上，路徑的左邊總共有幾個洞。如果要讓此一 query 的效能也維持住，修改的方式是讓每一個 internal node 記錄自己 subtree 裡總共有幾個洞 (或是有幾個實體值，這兩個值互補可以換算)。每一個小段更新這個資訊的耗時是 O(lgN)，使用時也是 O(lgN)，不過空間會多用不少，每一個元素都需要搭配一個可以存得下長度的格子。