12_10_docx

Size: px

Start display at page:

Download "12_10_docx"

皮管孔
5 years ago
Views:

1 字典樹 Trie 字典樹 (Trie), 也被稱為單詞搜尋樹, 是一種很特別的樹狀資料結構, 如同其名, 它就像一本字典, 可以讓你快速的依照字母插入尋找字串, 由於高效的特性, 特別適用於大量字串出現的時候字典樹的性質 Property of Trie 與二分搜尋樹堆積等利用鍵值來建立的資料結構不同, 字典樹最特別的地方就是善用字串的特性 : 利用每個字的共同前綴 (common prefix) 當儲存依據, 並以此來節省儲存空間以及加速搜尋時間利用樹狀結構, 我們將每個節點 (Node) 代表一個字母 ( 但根節點 (Root) 不能包含任何字母, 為什麼?), 每個節點的最大分支度為, 每個子節點分別代表字串的下個字母, 而整棵樹的高度則為最長字串的長度 + 1 ( 為什麼?) 從根節點往下走訪根節點往下走訪到的每個節點都可能代表一個字串 ( 字串長度為節點深度 -1), 不一定僅限於葉子 ( 為什麼?), 而每個字串的共同前綴都只會儲存一次, 有著共同前綴的字串們會被擺在一起, 並從代表從最長共同前綴以下才開始分歧, 也就是說, 最長共同前綴發生於代表兩字串節點的最近共同祖先 (Least Common Ancestor LCA) 上字典樹的資料結構實作 Data Structure of Trie 因為不知道之後字串的數量與長度, 所以通常用指標 (pointer) 實現, 與普通的樹 Tree 相同, 我們在節點中加入個指向子節點的指標 ( 亦代表子節點子節點的字元 )*Next, 同時, 為了判斷字串是存在, 在節點中記錄字串出現次數的 count 就是這麼簡單! (PS. 當及最大字串長度不大時, 也可以利用普通的陣列 (array) 及遞迴實現 ) 建立一棵字典樹 Create a Trie 雖然是以指標建立的, 但是還必須要有根節點根節點才有辦法進行接下來的一連串動作, 需要注意的是, 當新增一個節點時 ( 包括現在的根結點以及之後的子孫 ), 記得要把裡面的東西歸零裡面的東西歸零 STRUCT TRIE{ 1 INT count ; 2 STRUCT TRIE *Next [ ] ; }; CREATE-A-TRIE() 1 root new TRIE* 將字串插入 / 刪除 Insert/Delete a String into/from Trie 既然每個字串都一定會有唯一一個獨一無二的節點 ( 包含空字串 ), 當我們需要加入字串或從字典樹中刪除字串的時候, 就只需要更動該節點的 count 值即可並且這個節點會從根節點按照字元逐深度往下逐深度往下的深度為長度 +1 的節點, 使得我們可以用 Θ(length) 的時間找到這個節點! 這裡有個地方需要注意一下 : 因為是採用指標方式的, 所以當 tmp 要轉移到 Next 時, 該指標有可能是尚未建立的情況, 這時需要另外新增一個指標 INSERT(S) / DELETE(S) 1 len length of S 2 tmp root 3 for i 1 to len 4 do if tmp->next[s[i]] = 5 then tmp->next[s[i]] new TRIE* 6 do tmp tmp->next[s[i]] 7 tmp->count tmp->count ± 1

2 查尋字串 Look up a String in Trie 與插入刪除相同, 直接判斷該節點的 count 值即可, 複雜度為 (length) 若是中途發現無法轉移到下個字母, 就代表該字串一定不存在, 可直接判斷 false 釋放記憶體 Release the Memory of Trie 當字典樹用完之後, 記得要將記憶體釋放記憶體釋放, 否則再開一個字典樹的時候空間會不夠用釋放的方式可以用遞迴遞迴輕鬆實現, 釋放記憶體的複雜度是 ( 節點個數 ) LOOK-UP(S) 1 len length of S 2 tmp root 3 for i 1 to len 4 do if tmp->next[s[i]] = 5 return false 6 do tmp tmp->next[s[i]] 7 return tmp->count > 0 RELEASE(TRIE P) 1 for i 1 to 2 do if P->Next[ [i]] 3 then RELEASE( P->Next[ [i] ] ) 4 delete P 利用字典樹進行字串排序 Sorting Strings with Trie 這是字典樹的一個小應用, 字典樹就像字典字典一般, 按照字母查詢並印下來就會是一個順序的關係, 所以按照字母順序按照字母順序進行字典樹的深度優先搜尋 (DFS) 就可以輕易地做到字串排序, 複雜度是 ( 節點個數 ) 字典樹的優缺點 Trie 最大的優點就是運作速度非常快且容易撰寫, 針對查詢是否存在是否存在以及前綴相關前綴相關的問題幾乎都有非常好的效果, 但缺點就是相當耗費記憶體, 雖然已經把共同前綴合併, 但每個節點上面還是有著個指標, 且大部分情況下都會存在大量的空指標大量的空指標, 用的時候需要斟酌一下除了 Trie 字典樹外, 還有一種東西叫做 Trie 字典圖, 在多 pattern 時也有頗大的作用, 有興趣的話可以找找資料 UVAOJ Hardwood species 給定很多字串, 要求按照字母順序輸出每個字串在輸入中的百分比 UVAOJ Crables 給定一個最多字的字典, 最多玩一千次拼字遊戲, 每次玩最多有十張字母卡, 每張卡片都有一個字母跟分數 ( 相同字母可有不同分數 ), 求能組合出來的最大分數為和?( 分數為拼字用的各字母卡分數的和, 且一定存在拼字的方案 ) UVAOJ 644 Immediate Decodability 給定很多由 01 字串組成的 Group, 要算出每個 Group 是否是好的一個好的 Group 定義為 : 裡面的任一字串都不是裡面的任意字串 ( 不含自己 ) 的前綴 UVAOJ 409 Excuses,Excusess! 給定很多關鍵字, 還有很多藉口, 要求輸出關鍵字最多的藉口 ( 可重複計算 ) USACO TRAINING CHAP 2.3 The Longest Prefix(prefix) 給定一個字串集合以及一個大寫字母序列, 求由字串集合中字串組成的序列最長前綴 PKUOJ 3630 Phone List 給定一個字串集合以及一個大寫字母序列, 求由字串集合中字串組成的序列最長前綴 PKUOJ 3376 Finding Palindromes 給定很多字串, 問任取兩個字串接在一起, 有多少組回文

3 線段樹 Segment Tree 線段樹 (Segment Tree, Seg Tree) 是一種很特殊的二分搜尋樹, 用來儲存關於線段 ( 或區間, 但其與另外一種資料結構區間樹 (Interval Tree) 不一樣, 雖然很多資料兩個名詞都有互用且有點類似, 但兩者有實質上的不同 ) 的性質, 像是蓋了很多條線段之後, 查詢 [a,b] 被幾條線段覆蓋某區間內的極值等等, 並能在資料的頻繁更動中高效地維持性質 ( 動態維護 ) 樹本身的一個很重要的概念就是分割, 而普通 BST 等只能依據數據來進行, 但線段樹處理的卻是線段, 線段可以分割以及合併, 所以線段樹可以做到一些普通 BST 做不到的操作, 而時空複雜度也有別於一般的 BST 線段樹的性質 Property of Segment Tree [1,7] 線段樹是一種動態的二分搜尋樹, 其將區間 [1,L] 逐漸二分, 最後分割成一個個 [k,k+1] 的單位區間, 而每個節點都代表一個區間, 但唯有葉子是單位區間 [1,2] [2,4] [4,5] [5,7] 若節點 k 代表的區間為 [a,b], 則該節點的左子樹代表 [a, 右子樹代表而當要獲得 [a,b] 的資訊時, 我們可以直接使用 [2,3] [3,4] [5,6] [6,7] 節點上的訊息, 不必從 [a,a] 到 [b,b] 如此費時的搜尋線段樹處理的範圍必須預先設定好 ( 於根結點上 ), 否則會無從二分起, 空間也開不起來一個 [1,L] 的線段樹最大高度不會超過 log L 1 +1, 而在切割後會分成不超過 log L 條線段 [1,4] 考慮最差的空間複雜度,L+ + 2L, 所以空間複雜度為 O(L) 線段樹的資料結構實作 Data Structure of Segment Tree [4,7] 由於線段樹的範圍是固定的, 所以可以類似堆積 (Heap) 的方式用陣列 (array) 模擬 (Left->2n,Right->2n+1), 但資料量大的時候還是建議用指標 (pointer) 避免不必要的消耗以節省空間在節點中需要記錄所代表的區間 ( 也可不記錄, 以參數在遞迴表現 ) 以及被覆蓋的次數, 若用指標方式撰寫, 則需要納入兩個指標分別指向左子樹及右子樹, 用陣列則可以直接依據索引值移動依據索引值移動 STRUCT SEGTREE{ 1 INT leftside,rightside; 2 STRUCT SEGTREE *leftchild; 3 STRUCT SEGTREE *rightchild; 4 INT count; }; 建立一棵線段樹 Create a Segment Tree 若是以指標建立的, 必須要有根節點根節點才有辦法進行接下來的一連串動作, 若用陣列的話, 只需要改變根節點改變根節點即可, 需要注意的是, 當新增一個節點時 ( 包括現在的根結點以及之後的子孫 ), 記得要將左右界設定以及歸零歸零的動作做好將線段插入 / 刪除 Insert/Delete a Segment 因為線段樹是二分的, 所以可以很合理的想到用遞迴來實現操作在二分的過程中有兩種情況, 一種是要找的區間有被節點的中點切開, 一種是沒有, 若是前者就要進行二分的動作, 後者則是直接找一邊遞迴下去即可不過要注意指標尚未指向子樹的情況注意指標尚未指向子樹的情況因為在每一層的操作都是 O(1), 所以複雜度為 O(h),h 為樹的高度, 約為 log R L CREATE-A-SEGMENT-TREE(L,R) 1 root new SEGTREE* 2 root->leftside L 3 root->rightside R 4 root->count 0 INSERT/DELETE(SEGTREE P,INT L,INT R) 1 if P->leftSide = L and P->rightSide = R 2 then P->count P->count±1 3 else 4 mid (P->leftSide + P->rightSide) 2 5 if L mid and R mid 6 then INSERT (P->leftChild, L,mid) 7 INSERT (P->rightChild, mid, R) 8 else if L > mid 9 then INSERT (P->leftChild, L,R) 10 else then INSERT (P->rightChild, L,R)

4 線段樹的擴充 Expansion of Segment Tree 除了紀錄完全覆蓋的線段個數 count 外, 通常我們還會紀錄一些其他的資訊以解決更多問題一區間內被覆蓋的總長度 cover 二區間內互不相交的線段數 line 三區間內所有單位線段的權重和 sum 而以上資訊都可以在插入刪除時於遞迴的過程中獲得, 可以思考一下要如何實現釋放記憶體 Release the Memory of Segment Tree 當線段樹用完之後, 記得要將記憶體釋放記憶體釋放釋放的方式可以用遞迴遞迴輕鬆實現, 釋放記憶體的複雜度是 ( 節點個數 ) 線段樹的變化 Variations of Segment Tree RELEASE(SEGTREE P) 1 do if P->leftChild 2 then RELEASE( P->leftChild ) 3 do if P->rightChild 4 then RELEASE( P->rightChild) 5 delete P 一離散化 (Discretization): 基本的線段樹的節點所含的是兩點之間的區間, 而單位線段, 則是長度固定為 1 的線段, 但若將線段離散成點來看, 只將我們需要的區間留下線段樹的離散化又分為兩種, 一種是將連續線段離散成可連續的點, 另一種是將線段離散之後每一小段都視為一個單位線段來建立線段樹二樹狀數組 (Binary Indexed Tree) 例題一線段問題 Stabbing Problem 給定一些平面上的線段, 問一條 x = a 的垂直線 L 會與哪些線段相交例題二垂直線段相交問題給定很多垂直線段以及水平線段, 請求出所有的交點例題三 TIOJ 1224 矩形覆蓋面積計算給定平面上很多矩形, 矩形的四邊都與座標軸垂直或平行, 求出他們覆蓋平面的總面積例題四 TIOJ 1382 約瑟問題 Josephus Problem 有 n 個人圍成一圈, 從編號 1 開始數, 每數 Ai 個人就要離開圓圈, 求每人離開圓圈的順序例題五神秘的詢問 Mysterious Queries 有 n 個數字排成一排, 一開始他們都是 0, 現在可以最這排數字做一些操作, 將某個數字改掉, 或是詢問第 i 個到第 j 個數字當中最大的是多少例題六 PKUOJ 1610 Count Color 給定一條線段 [1,L], 有兩種操作 : 在 [A,B] 塗上 C 色查詢 [A,B] 有幾種顏色, 顏色最多 30 種例題七 TIOJ 1272 The Agency 給定一棵樹, 編號 1 永遠是根, 每個節點一開始都是白色的, 你可以有兩種操作 : 將一個節點以及他的所有子孫變色或是查詢某個節點的顏色例題八壞掉的小畫家 Broken Painter 小畫家壞掉了, 現在只能拿來畫矩形, 而且每畫出一個矩形, 該矩形內的顏色就會變成互補色 ( 黑白互變 ) 你可以有兩個動作 : 畫出一個矩形或是查詢座標 (x,y) 的顏色

5 樹狀數組 Binary Indexed Tree 樹狀數組 (Binary Indexed Tree, BIT) 是線段樹的一種變形, 由 Peter M. Fenwick 於 1994 年提出與線段樹類似, 樹狀數組也是用來維護區間的特性, 但其運用了 2 進位的概念, 是得其能更高效能且低撰寫複雜度地維護一些性質樹狀數組的性質 Property of Segment Tree 樹狀數組巧妙地運用了一個數字能經由多個 2 的數字組成, 以達到高效維護的工作定義 p 為 k 轉換成二進制後最後一位不為 0 的位元 (LowBit), Tree[ k ] 則代表第 k-p+1 個元素到第 k 個元素的性質 ( 即維護 p 個元素的性質 ) 我們發現, 任何一個 [1,L] 的區間所維護的性質, 都可以從 Tree[k] 中得到! 以 [1,11] 來說, 就是 : [1,11] Tree[11] Tree[10] Tree[8] 化為 2 進位來看 : [1,11] Tree[1011] Tree[1010] Tree[1000] 很明顯地, 區間 [1,L] 的性質可以經由逐漸將 L 的 LowBit 減掉, 在合併資訊所以我們又可以以另外一種方式定義樹狀數組 : [1,L] Tree[k] Tree[k-LowBit(k)] Tree[k-LowBit(k)-LowBit(k-LowBit(k))]... 經由這種巧妙的結構, 原本需要花費 O(n) 的工作, 現在只需要耗費最多 O( ) 的時間就可完成不過值得注意的是, 因為 0 無法處理 LowBit, 所以樹狀數組能夠處理的範圍為 [1,L] 樹狀數組的資料結構實作 Data Structure of Binary Indexed Tree 因為是直接依據二進制操作, 所以樹狀數組的資料結構非常簡單, 只要一個陣列 (array) 就好了! 不過需要注意大小一定要開 [L+1], 因為樹狀數組的操作範圍是 [1,L] 1 DATATYPE Tree[ L+1 ]; LowBit 函數 How to find LowBit 樹狀數組中的一大重點就是要如何找到轉換成二進制後最後一位不為 0 的位元 (LowBit), 如果每次都要掃描一次, 既費時太麻煩了! 於是我們利用補數補數的概念找到了一個簡單方便的方法 : k & -k! 為什麼這會是對的呢? 思考一下當 k 變成 k 之後的模樣, 我們假設 k 的二進制為 a1b,a 是 LowBit 之前的數字,b 是之後的 0, 因為補數的關係, 所以我們可以得到 : LOWBIT(INT idx) 1 return idx & -idx k= a1b +1 = a 0b +1 = a = a 1b a 與 a and 之後為 0,b 也都是 0, 因此, 我們將 k 以及 k 作 and 之後就會是 k 的 LowBit 了! 查詢樹狀數組紀錄的資訊 Find with BIT 按照樹狀數組的性質, 在持續減掉 LowBit 的過程中我們可以從中獲得資訊, 複雜度為 O(log L) 更新樹狀數組紀錄的資訊 Update BIT 與查詢相反, 更新資訊需要做的就是把牽扯到自己的資料更新, 方法也與查詢相反, 持續加上 LowBit 即可, 複雜度為 O(log L) FIND(INT L) 1 ans 0 2 for i L to 0 + step LowBit(i) 3 do ans ans Tree[i] 4 return ans UPDATE(INT X,DATATYPE D) 1 for i X to L step LowBit(i) 2 do Tree[i] Tree[i] D

6 樹狀數組的擴充 Expansion of Binary Indexed Tree 因為操作方便的關係, 樹狀數組可以輕易做到多維多維的以二維來說, 就是維持 [1,1] 到 [m,n] 所形成矩形區域的性質, 三維則是長方體, 擴充到 n 維的樹狀數組複雜度為 O( log L ) 樹狀數組的優缺點樹狀數組最令人讚嘆的就是其效率及撰寫複雜度, 很多需要使用繁鎖線段樹的問題, 使用樹狀數組就迎刃而解, 就連多維操作多維操作也可以輕易達成但樹狀數組也不是萬能的, 最讓人詬病的就是其空間的限制, 範圍有多長就得開多少, 無法節省空間, 頂多使用離散化離散化節省一下, 但也僅限於靜態操作靜態操作時, 若是動態操作就沒轍了樹狀數組另外一個弱點就是維護範圍, 其只能只能求出 [1,L] 的性質, 無法求出任意區間的性質, 所以只有具有排容性質的資料在樹狀數組中才能求出任意區間的性質, 而且關於極值的性質就只能插入不能刪除了 ( 因為不知道在哪裡 ) 例題一 URAL 1028 Stars 給定很多星星的座標, 一個星星的級別是不在它上面且不在它右面的星星的總數, 求每個級別星星數例題二 TIOJ 1493 三個農夫給定一棵樹, 可以進行兩種操作, 在節點上種編號 1~3 的水果 (1 不能種葉子 23 不能種根 ), 或是查詢某節點以上每種水果各有多少個例題三 TIOJ 1483 TCPC08 pj 電腦檢查給定一個矩陣, 問二維 Increasing Sequence 個數例題四 TIOJ 1266 保加利亞的俄羅斯娃娃給定一個矩陣, 問二維 Longest Increasing Sequence 下面是一些有關線段樹與樹狀數組的題目 : PKUOJ 2528 Mayor s posters 在一條 [1, ] 的布告欄上貼最多張海報, 可能會重疊, 求最終看到海報數量 USACO TRAINING CHAP 5.5 Picture(picture) 給你很多張貼在牆上的矩形海報, 可能會重疊, 求最終輪廓的周長 PKUOJ 1195 Mobile Phones 三個動作 : 產生一個 S*S 的矩陣並將其歸零將矩陣中某一格加一數字查詢某子矩陣和 PKUOJ 3067 Japan 給定左岸 n 座城市, 右岸 m 座城市,k 座筆直連結兩岸兩城市的高速公路, 問總共有幾個交叉點 PKUOJ 3264 Balanced Lineup 有 n 條牛站在一起, 每條牛有身高,Farmer Jiang 有很多詢問, 每次問第 A 條牛到第 B 條牛之間, 最高的牛跟最低的牛身高相差多少

Microsoft Word - _m30.doc

Microsoft Word - _m30.doc 1 2 3 4 5 6 7 8 公式 2 4 2 1 能整除因此後玩者贏且關鍵數字為3 的倍數 3 0 3 1 不能整除所以先拿餘數 2 關鍵數字是 4的倍數 2 先玩者贏 4 0 4 1 能整除因此後玩者贏且關鍵數字為 5 的倍數 5 0 5 1 不能整除所以先拿餘數 2 關鍵數字是 6的倍數 2 先玩者贏 7 0 6 1 能整除因此後玩者贏且關鍵數字為7