Sequence資料結構: Array / List

Array

儲存一個數列,直覺的方式是使用一個陣列。

更新第k項:O(1)。

插入第k項、刪除第k項:需要挪移資料。O(N)。

區間總和、區間最大值、區間最小值:逐個累計。O(N)。

List

更新第k項、插入第k項、刪除第k項:需要定位。O(N)。

區間總和、區間最大值、區間最小值:逐個累計。O(N)。

串列與陣列的步驟數量,相比之下,顯然串列小於等於陣列──然而兩者的時間複雜度都是O(N)。可以發現現行的時間複雜度標記方式,不是那麼精準,無法區分兩者的快慢差異。

Unrolled Linked List

更新第k項:O(A)。

插入第k項、刪除第k項:O(A + 2B)到O(2A + B)。

使用sqrt decomposition,三者皆是O(sqrtN)。

區間總和、區間最大值、區間最小值:每塊額外記錄數值,先查詢塊、再查詢元素。O(A)到O(A + 2B)。

使用sqrt decomposition,三者皆是O(sqrtN)。

如果只需更新、查詢,不需插入、刪除,此時可以用陣列代替串列,容易實作。

UVa 12003 11922 11990 12345

Sequence資料結構: Binary Search Tree

粗淺的理解、錯誤的方式

既然BST是儲存大量數字的資料結構,我們嘗試運用BST來儲存一個數列。

數列的索引值是有序的,BST是有序的,我們嘗試以索引值大小順序,做為BST的排序依據。BST的每個節點,額外記錄數列的數值。

雖然可以迅速更新第k項,但是無法迅速插入第k項、刪除第k項,索引值無法保持連續整數。

深刻的理解、正確的方式

Search Tree、Heap的功能是排順序,排序依據不見得得是數字大小順序,排序依據也不見得要儲存於節點之中。比如圖論領域的資料結構「Link-Cut Tree」所使用的BST,排序依據是樹上節點的父子順序。

令左子樹是索引值較小的項、右子樹是索引值較大的項。排序依據,仍是索引值大小順序,但是排序依據不必儲存於節點之中。

更新第k項:就是找到BST第k名。BST的每個節點,額外記錄子樹的節點個數,以便快速得到名次。

插入第k項:先找到BST第k名,如果沒有右小孩,就挪至右小孩;如果擁有右小孩,就挪至次大節點(即BST第k+1名)的左小孩。然後原本第k名的位置,存入數列第k項。最後記得更新擴充資訊,由樹葉往樹根方向。

刪除第k項:先找到BST第k名,如果沒有小孩,就直接刪除;如果擁有左小孩、沒有右小孩,就拿左子樹頂替第k名;如果擁有左小孩、擁有右小孩,就拿次大節點頂替第k名,再拿次大節點的右子樹頂替次大節點(此時次大節點無左小孩)。最後記得更新擴充資訊,由樹葉往樹根方向。

不必死背這些流程。只要細心觀察BST,很容易推理出來。

如果旋轉節點、平衡BST,那麼更新、插入、刪除、尋找次大節點的時間複雜度從O(N)變成O(logN)。

區間總和、區間最大值、區間最小值:每個節點額外記錄該子樹所有節點的總和、最小值、最大值!交給讀者。

任意區間的最大(小)區間和:交給讀者。

Sequence資料結構: “Fake” Segment Tree

“Fake” Segment Tree【尚無正式名稱】

此資料結構由競賽選手發明,沒有發表為正式的學術論文。目前發現最早出現於Baltic OI 2001: Mars Maps,官方解答提供了此資料結構的程式碼。

此資料結構最初沒有特定名稱。傳入中國之後,競賽選手將名稱定調為Segment Tree,創造大量相關題型,例如SPOJ: GSS3,令Segment Tree之名稱被發揚光大。然而「Segment Tree」是既有的資料結構名稱,所以此資料結構勢必另取他名,以免混淆。

建立資料結構

遞迴二分區間,樹葉存放數列,一個樹葉儲存一項;非樹葉存放擴充資訊,諸如區間總和、區間最大值、區間最小值。

節點最多是2N-1個,空間複雜度為O(N),時間複雜度為O(N)。N為數列長度。

更新第k項、區間總和、區間最大值、區間最小值

類似二元搜尋樹,時間複雜度為樹的深度O(logN)。

UVa 11297 12299

插入第k項、刪除第k項

不負責任地交給讀者。

任意區間的最大(小)區間和

不負責任地交給讀者。

ICPC 3938

推廣到高維度

偽線段樹可以推廣到高維度,從一維數列變成二維陣列、三維陣列。二維偽線段樹,是先製作一棵第一維度的偽線段樹(稱作X樹),然後每個節點各自接上一棵第二維度的偽線段樹(稱作Y樹)。中文網路稱作「樹套樹」。

UVa 12698

更新區間:楔子

偽線段樹也可以更新區間。首先簡化問題,把數值改成顏色。如果區間不是相同顏色,就繼續遞迴對半分割下去。如果區間是相同顏色,暫且不分割!

更新第k項,有三大步驟:一、搜尋之時,原有顏色分離,挪往下層。二、就位之時,直接覆蓋顏色,刪除子樹(或者無視子樹)。三、回溯之時,相同顏色合併,挪往上層。

此番技巧尚未有正式名稱,英文網路稱作「lazy propagation」,中文網路稱作「延遲標記」。

更新區間:視情況左右子樹都得走,並分割更新區間。

查詢第k項:一旦遭遇顏色,即得答案,不必深入子孫。

查詢區間顏色是否一致:視情況左右子樹都得走,並分割查詢區間。當節點區間大於等於查詢區間時,一旦遭遇顏色,即可判斷異同,不必深入子孫。當節點區間小於等於查詢區間時,一旦遭遇無色,即得答案為否,不必深入子孫。不能推廣到高維度。

這四項操作的時間複雜度都是O(logN)。

更新區間:統統改為一數值

更新第k項、更新區間:運用「lazy propagation」技巧,凡遭遇已改值的區間,則分離挪往下層。

查詢第k項、查詢區間:凡遭遇已改值的區間,即得答案,不必深入子孫。

查詢區間不能推廣到高維度。

更新區間:統統增減一數值

更新第k項、更新區間:直接在對應區間累計增減值。

查詢第k項:累加路線上的增減值。

似乎無法查詢區間。

這似乎也被歸類於「lazy propagation」技巧。

UVa 11402 11992

Bottom-up “Fake” Segment Tree【尚無正式名稱】

BST和FST要實作很久,趕時間的競賽選手避之唯恐不及。如果不需要插入第k項、刪除第k項,只需要更新第k項、查詢區間,此時就可以採用特殊資料結構,編寫較少程式碼。

只能更新第k項、查詢區間:Bottom-up “Fake” Segment Tree
只能更新第k項、查詢區間總和:Binary Indexed Tree
只能更新第k項、查詢區間極值:Sparse Table

2010年由競賽選手清华大学张昆玮《统计的力量——线段树全接触》提出。我不清楚是否已有正式學術論文。

讀者須具備「Bitwise Operation」基礎。

Sequence資料結構: Binary Indexed Tree

Binary Indexed Tree(Fenwick Tree)

存放一串數列,可以快速算出任意區間的總和。

可以更新數值,但是不能插入、刪除數值。

閒置陣列第零格。觀察前綴和,切割成數段。切割方向:索引值由小到大。切割長度:二的次方,數量級盡量大。

索引值化作二進位,上述行為即是:索引值逐次刪去最低位的1。

10的二進位是1010。
刪去最低位的1,切割成 1010 ~ 1000+1,剩下1000。
刪去最低位的1,切割成 1000 ~ 0000+1,剩下0000,結束。

7的二進位是111。
刪去最低位的1,切割成 111 ~ 110+1,剩下110。
刪去最低位的1,切割成 110 ~ 100+1,剩下100。
刪去最低位的1,切割成 100 ~ 000+1,剩下000,結束。

每種前綴和,皆實施切割,總共只有N種區段!N個區段和,依序儲存於陣列,得到Binary Indexed Tree。是陣列、不是樹。

Binary Indexed Tree得視作偽線段樹的精簡版本:擴充資訊是區間總和;移除樹根及全部右小孩。

計算第1項到第k項的總和

挑出對應的區段,進行累加。

更新一項數值

看看哪些區段包含這一項,補上差值。

複雜度

建立時間為O(NlogN),建立空間為O(N),更新一項數值的時間是O(logN),計算任意區間總和的時間是O(logN)。

註:採用偽線段樹的建立手法,建立時間變為O(N)。

UVa 11423 11610

推廣到高維度

Binary Indexed Tree可以推廣到高維度,建立方法是逐步處理各維度。以二維為例:矩陣切成一條一條的橫條,每個橫條分別建立BIT,每個橫條都有N種區段;然後針對每一種區段,再分別建立垂直方向的BIT。

建立時間為O(XlogX * YlogY * ...),建立空間為O(XY...),更新一項數值的時間是O(logX * logY * ...),計算任意矩形區域總和的時間是O(2^D * logX * logY * ...)。

UVa 11601

Sequence資料結構: Sparse Table

Sparse Table【註:古代名稱,今日看來詞不達意。】

存放一串數列,可以快速算出任意區間,其中一個最小(大)值的所在位置。有人稱作Range Minimum Query問題。

不能更新、插入、刪除數值。

依序求出寬度為1、2、4、8、……的區間最小值,區間的所有可能位置都要算一遍。兩個窄區間可以快速合成出一個寬區間。

將寬度為1、2、4、8、……的區間最小值,儲存於表格。

t(i, j) =
 { min{ t(i-1, j), t(i-1, j+2^(i-1) }  , if i > 0
 { value[j]                            , if i = 0

實作時,通常表格中記錄的是索引值、指標,而不是直接記錄數值的最小值。

計算區間最小值(的索引值)

查詢時,先從表格中找到寬度略短於(相等於)查詢區間的區間,以靠左、靠右的兩條等寬區間,求得查詢區間的最小值:

複雜度

建立時間為O(NlogN),建立空間為O(NlogN),計算任意區間最小值的時間是O(1)。

UVa 11235

推廣到高維度

這個資料結構可以推廣到高維度,建立方法是逐次處理各維度即可。以二維為例,先把矩陣切成一條一條的橫條,每個橫條都建立1D Sparse Table;然後以第一條橫條的表格為基礎,表格中的每一個子問題,都建立垂直方向的1D Sparse Table,如此便完成了二維的版本。

建立時間為O(XlogX * YlogY * ...),建立空間為O(XlogX * YlogY * ...),計算任意矩形區域最小值的時間是O(2^D)。

UVa 11263

Sequence資料結構: Cartesian Tree

Cartesian Tree

http://web.engr.illinois.edu/~jeffe/teaching/algorithms/notes/10-treaps.pdf

Cartesian Tree是一種Treap,根的數值小於左右子樹,根的索引值介於左右子樹。

以online方式建立,由左到右讀取陣列元素,每讀取一個元素,就建立一個節點。整棵樹剛好依照DFS順序來回遍歷一次。通常使用stack實作,確保stack的元素依序排好。

All Nearest Smaller Values

http://en.wikipedia.org/wiki/All_nearest_smaller_values

±1 Range Minimum Query

RMQ問題,以O(N)時間建立Cartesian Tree,便化作LCA問題。

LCA問題,以O(N)時間用DFS遍歷,記下到訪次序(作為索引值)、深度(作為元素值),便化作±1RMQ問題。

±1RMQ問題有著特殊的演算法,建立時間為O(N)、查詢時間為O(1),到達理論下限。然而±1RMQ規則複雜,實務上效率極差,此處不介紹,請讀者自行尋找資料。

RMQ問題、LCA問題、±1RMQ問題的時間複雜度皆相等,而且到達理論下限。也就是說這三個問題已經被徹底解決了。

Sequence資料結構: Quicksort Tree

Quicksort Tree【尚無正式名稱】

http://yueyue1105.blog.163.com/blog/static/431117682010716111425892/

top-down建立。以中位數作為pivot,預先排序以求得中位數。

建立O(NlogN)、修改O(logN)、無法插入及刪除、查詢區間內第k名元素O(logN),查詢區間內元素名次O(logNlogN)。

Wavelet Tree

即是Succinct Quicksort Tree。

http://alexbowe.com/wavelet-trees/

Sequence資料結構: Mergesort Tree

Mergesort Tree【尚無正式名稱】

http://yueyue1105.blog.163.com/blog/static/431117682010716111425892/

bottom-up建立。

建立O(NlogN)、修改O(logN)、無法插入及刪除、查詢區間內第k名元素O(logNlogN),查詢區間內元素名次O(logNlogN)。