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」是既有的資料結構名稱,所以此資料結構勢必另取他名,以免混淆。

建立資料結構

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

二元樹的資料結構,採用陣列,投機取巧省去new和delete。

進一步重新配置節點位置,節省記憶體空間。節點[L,R]配置於陣列第L+R格。

原理如同二元搜尋樹,左子樹L+R較小或相等、右子樹L+R較大,導致每個節點的L+R皆相異,例外是樹葉與非樹葉之間的L+R可能相等,此時樹葉配置於原本位置、非樹葉配置於下一格。

節點總共2N-1個,陣列總共2N-1格。空間複雜度O(N),時間複雜度O(N)。N是數列長度。

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

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

UVa 11297 12299

插入第k項、刪除第k項

不負責任地交給讀者。

推廣到高維度

一維數列推廣到二維陣列、三維陣列。

二維偽線段樹,首先製作一棵第一維度的偽線段樹(X樹),然後每個節點各自接上一棵第二維度的偽線段樹(Y樹)。中文網路稱作「树套树」。

UVa 12698

更新區間:楔子

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

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

此技巧尚無正式名稱,英文網路稱作「lazy propagation」,中文網路稱作「懒惰标记」,翻譯錯誤。

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

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

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

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

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

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

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

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

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

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

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

似乎無法查詢區間。

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

UVa 11402 11992

sequence資料結構: bottom-up “fake” segment tree

楔子

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

只能更新第k項、查詢區間:bottom-up “fake” segment tree
只能更新第k項、查詢區間總和:binary indexed tree
只能更新第k項、查詢區間極值:sparse table

bottom-up “fake” segment tree【尚無正式名稱】

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ᴰ ⋅ 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ᴰ)。

UVa 11263

sequence資料結構: quicksort tree

quicksort tree【尚無正式名稱】

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

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

succinct quicksort tree(wavelet tree)

sequence資料結構: merge sort tree

merge sort tree【尚無正式名稱】

bottom-up建立。

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

persistent merge sort tree【尚無正式名稱】

插入及刪除O(logN)。

sequence資料結構: Cartesian tree

Cartesian tree

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

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

僅有理論上的價值,沒有實務上的價值。

all nearest smaller values

±1 range minimum query

尋找區間最小值所在位置,當陣列相鄰數值總是相差±1。

RMQ問題化作LCA問題:利用Cartesian tree。O(N)。

LCA問題化作±1RMQ問題:利用Euler tour technique。DFS到訪次序(作為索引值)、深度(作為元素值)。O(N)。

±1RMQ問題:演算法相當複雜,此處不介紹。建立O(N)、查詢O(1)。

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

僅有理論上的價值,沒有實務上的價值。

sequence特殊技巧: cumulative sum / adjacent difference

cumulative sum / adjacent difference

累積和(離散積分):從頭開始、連續數字和。

相鄰差(離散微分):相鄰數字差。

兩者可以相互抵消!次數一樣多,得到原數列。

數列  4 -1  6  0  9
累積和 4  3  9  9  18
相鄰差 4 -5  7 -6  9

區間和

預先以O(N)計算累積和,便能以O(1)計算區間和。

二元搜尋樹

集合(索引儲存)、數列(偽線段樹、binary indexed tree)、累積和、二元搜尋,取代二元搜尋樹的各種功能。

集合freq[i]
替freq[i]建立數列資料結構
freq[n]++                <---> 插入數字n     O(logN)
freq[n]--                <---> 刪除數字n     O(logN)
freq[n]累積和            <---> 數字n的名次   O(logN)
freq[n]累積和,二元搜尋k <---> 第k大的數字   O(log²N)

UVa 11525 11990 ICPC 4329

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

數列a[i]、數列相鄰差d[i]
替d[i]與i×d[i]建立數列資料結構
d[i]左界+n右界-n <---> a[i]區間+n   O(logN)
d[i]累積和       <---> a[i]第k項    O(logN)
d[i]累積和累積和 <---> a[i]累積和   O(logN)
(用d[i]和i×d[i]算)

sequence特殊技巧: minimum stack / minimum queue

minimum stack / minimum queue