高級數(shù)據(jù)結構

高級數(shù)據(jù)結構選講 杭州第二中學李建手機Q 43075478 一 一個學生從零到NOI金牌需要經(jīng)歷哪些階段 二 在這些階段中我們需要做好哪方面的工作 NOIP階段 NOI階段 一 一個學生從零到NOI金牌需要經(jīng)歷哪些階段 二 在這些階段中我們需要做好哪方面的工作 在NOIP階段 我們需要將學生領入信息學這個陌生的世界 需要我們手把手教學生寫程序 因此要求老師能夠自己能夠編寫代碼 能夠幫助學生查錯 幸運的是 該階段要求的算法理解及編寫復雜度并不高 到了NOI階段 算法的廣度和深度直接是呈 指數(shù)爆炸 的 并且經(jīng)常會有新潮的算法冒出來 此時再讓我們所有老師熟練運用相關算法就顯得太勉為其難 當然千古神犇老師除外 所以這個階段我們需要鍛煉學生的自主學習能力 但是讓學生自主學習并不是老師就徹底淪為一個機房管理員 我們需要讓學生有組織有模塊有系統(tǒng)的高效自學 而讓學生自主學習基本包含確定專題 尋找講稿 理解算法 代碼實現(xiàn) 學以致用 在這些過程中 我們需要思考我們有哪些環(huán)節(jié)可以參與進去 確定專題 保證學生不走彎路 循序漸進的學習 PS 連線段樹都不會就去學主席樹 那就糟糕了 尋找講稿 某度上講稿參差不齊 學生經(jīng)?？戳撕芫?不理解是正常的 理解了的發(fā)現(xiàn)講稿是錯的事情也常有發(fā)生 所以我們老師需要幫學生篩選講稿 讓學生不至于浪費時間 理解算法 篩選講稿的時候已經(jīng)要求我們老師去理解這個算法 我們不一定必須將代碼實現(xiàn)出來 但是必須要理解其核心過程 在學生學習的時候也可以做相關講解 加快學生的學習進程 代碼實現(xiàn) 這個只能學生親自上場搏殺了 學以致用 在學生學習一個算法后 最后幫學生找3 5道例題 加以鞏固 本次交流的主要內容 恰巧前段時間剛組織學生學習了高級數(shù)據(jù)結構專題 我就將我學習的一些算法和大家一起交流分享一下 一 堆 用途 在線求最值存儲 插入 O logn 刪除 僅能刪除最值 O logn 詢問 O 1 一 堆 向下調整 以小根堆為例 二 并查集 二 并查集 路徑壓縮 避免鏈狀退化 三 分塊思想 包含n個元素的整數(shù)數(shù)組A 每次可以C i j 修改一個元素A i jQ i j 詢問A i A i 1 A j 的值如何設計算法 使得修改和詢問操作的時間復雜度盡量低 顯然存在修改O 1 查詢O n 的算法 從算法瓶頸處開始思考 否則僅僅是常數(shù)優(yōu)化 無法降低時間復雜度 三 分塊思想 每次重新計算 一些未被修改區(qū)間也經(jīng)常被重復求和 于是我們可以將A 1 n 均分成sqrt n 塊 每塊內部的元素為sqrt n 個 修改操作時只需要修改A i 及A i 所在的塊 詢問操作時是需要枚舉i和j所在的塊內部 及其之間的塊 時間復雜度在O sqrt n 級別 四 樹狀數(shù)組 在分塊思想的基礎上 我們進一步思考是否有比sqrt n 更優(yōu)秀的分組方法 logn 基于2進制的分組方式 2進制變10進制是怎么做的 C i A i 2k 1 A i k為i在二進制下末尾0的個數(shù) 令LOWBIT i 2k通俗版本 C 52 110100 A 110100 A 110011 A 110010 A 110001 4 LOWBIT 52 52and 52xor 52 1 四 樹狀數(shù)組 Sum 52 110100 C 110100 C 110000 C 100000 修改操作 我們只需要思考A 110100 的修改會帶來哪些C 的改變 參考詢問的過程我們能夠輕易的發(fā)現(xiàn)O logn 級別的解決方案 至此 我們獲得了基于二進制且查詢和修改都是O logn 的算法 A 110100 A 110011 A 110010 A 110001 110000 110100 LOWBIT 110100 完美 五 線段樹 六 字母樹 Trie樹 通過樹結構來節(jié)省公共前綴的開銷 六 字母樹 Trie樹 應用 字符串排序 在字母樹上先序遍歷公共前綴計算 公共祖先字符串檢索 在字母樹上跑一遍即可 七 Treap 傳統(tǒng)旋轉式 Treap Tree 二叉搜索樹 Heap 期望平衡 七 Treap 傳統(tǒng)旋轉式 我們按照滿足二叉搜索樹的性質進行插入 因此我們需要一種不改變二叉搜索樹性質的情況下對Treap進行調整 使其滿足的堆的性質 以達到期望平衡 七 Treap 傳統(tǒng)旋轉式 我們按照滿足二叉搜索樹的性質進行插入 因此我們需要一種不改變二叉搜索樹性質的情況下對Treap進行調整 使其滿足的堆的性質 以達到期望平衡 七 Treap 傳統(tǒng)旋轉式 插入 七 Treap 傳統(tǒng)旋轉式 刪除 將要刪除元素的堆關鍵字改為最大值 一路旋到底查找 滿足二叉搜索樹性質分離 需要分開的位置添加一個堆關鍵字為0的虛點 一路旋到頂合并 兩棵樹之間滿足絕對大小關系 分離的逆操作時間復雜度分析 通過隨機的對關鍵字 達到期望平衡 故上述操作的復雜度均為O logn 八 笛卡爾樹 笛卡爾樹是一棵二叉樹 樹的每個節(jié)點有兩個值 一個為key 一個為value 光看key的話 笛卡爾樹是一棵二叉搜索樹 每個節(jié)點的左子樹的key都比它小 右子樹都比它大 光看value的話 笛卡爾樹有點類似堆 根節(jié)點的value是最小 或者最大 的 每個節(jié)點的value都比它的子樹要大 八 笛卡爾樹 巧妙的建樹方法 在按照key排序后 插入時通過堆棧實現(xiàn)value性質的滿足 棧中保存的是從根到最右邊那根鏈上的結點 從前往后遍歷Value i 1 對于每一個Value i 從棧中找出 從棧頂往棧底遍歷 第一個小于等于Value i 的元素Value j 2 將Value大于Value i 的點全部彈出3 在樹中 將j及其子樹掛在i上 將i掛在原來j的位置 八 左偏樹 為解決堆不能合并的問題 性質1 節(jié)點的鍵值小于或等于它的左右子節(jié)點的鍵值 即key i key parent i 這條性質又叫堆性質 符合該性質的樹是堆有序的 Heap Ordered 有了性質1 我們可以知道左偏樹的根節(jié)點是整棵樹的最小節(jié)點 于是我們可以在O 1 的時間內完成取最小節(jié)點操作 性質2 節(jié)點的左子節(jié)點的距離不小于右子節(jié)點的距離 即dist left i dist right i 這條性質稱為左偏性質 性質2是為了使我們可以以更小的代價在優(yōu)先隊列的其它兩個基本操作 插入節(jié)點 刪除最小節(jié)點 進行后維持堆性質 在后面我們就會看到它的作用 節(jié)點i的距離 dist i 是節(jié)點i到它的后代中 最近的外節(jié)點所經(jīng)過的邊數(shù) 節(jié)點i稱為外節(jié)點 externalnode 當且僅當節(jié)點i的左子樹或右子樹為空 九 左偏樹 合并 FunctionMerge A B IfA NULLThenreturnBIfB NULLThenreturnAIfkey B dist left A Thenswap left A right A 保證繼續(xù)左偏Ifright A NULLThendist A 0Elsedist A dist right A 1returnAEndFunction 九 左偏樹 插入 同合并刪除最小結點 直接刪除 再合并構建 方法一 直接不停單點插入 復雜度O nlogn 方法二 使用隊列 不斷將兩棵小的合并成一棵大的 復雜度O n 十 Treap 非旋轉式 傳統(tǒng)Treap在旋轉過程中會改變樹的形態(tài) 而在很多方面樹的形態(tài)改變會給我們帶來很多的麻煩 無法解決區(qū)間問題 無法很方便的打lazy標記 無法可持久化 左偏樹的合并方式給我們留下了無限的YY空間 需要保證左邊的所有元素小于 廣義的小于 根據(jù)平衡樹的作用來確定 位置 時間軸 右邊的元素 合并時 如果現(xiàn)在的左樹堆Value小于右樹 假設是小根堆 則調用merge 左樹 rson 右樹 返回值作為左樹的rson 因為右樹大于左樹 所以不會在左樹的左子樹遞歸調用否則調用merge 左樹 右樹 lson 十 Treap 非旋轉式 分割 假設我們需要將一個Treap分割成 1 k 和 k 1 N 具體見下圖 x K K 1 K 1 K K 1 x K 1 十 Treap 非旋轉式 建樹 參考笛卡爾樹插入 合并刪除 先分割處理后再合并區(qū)間操作 分割兩次分割出目標區(qū)間 區(qū)間操作 合并回去可持久化 每次維護一條新的鏈 具體見十六部分 十一 Splay SplayTree是二叉查找樹的一種 它與平衡二叉樹不同的是 SplayTree從不強制地保持自身的平衡 每當查找到某個節(jié)點n的時候 在返回節(jié)點n的同時 SplayTree會將節(jié)點n旋轉到樹根的位置 這樣就使得SplayTree天生有著一種類似緩存的能力 因為每次被查找到的節(jié)點都會被搬到樹根的位置 所以當80 的情況下我們需要查找的元素都是某個固定的節(jié)點 或者是一部分特定的節(jié)點時 那么在很多時候 查找的效率會是O 1 的效率 當然如果查找的節(jié)點是很均勻地分布在不同的地方時 SplayTree的性能就會變得很差了 但SplayTree的均攤時間復雜度還是O logn 的 十一 Splay 旋轉 樹的旋轉是splay的基礎 對于二叉查找樹來說 樹的旋轉不破壞查找樹的結構 十一 Splay 將x旋轉到根 受以下三種因素影響 節(jié)點x是父節(jié)點p的左孩子還是右孩子節(jié)點p是不是根節(jié)點 如果不是節(jié)點p是父節(jié)點g的左孩子還是右孩子 十一 Splay Zig操作當p為根節(jié)點時 進行Zig操作 當x是p的左孩子時 對x右旋 當x是p的右孩子時 對x左旋 十一 Splay Zig Zig操作當p不是根節(jié)點 且x和p同為左孩子或右孩子時進行Zig Zig操作 當x和p同為左孩子時 依次將p和x右旋 當x和p同為右孩子時 依次將p和x左旋 十一 Splay Zig Zag操作當p不是根節(jié)點 且x和p不同為左孩子或右孩子時 進行Zig Zag操作 當p為左孩子 x為右孩子時 將x左旋后再右旋 當p為右孩子 x為左孩子時 將x右旋后再左旋 十一 Splay 查找 i 可以從樹t的根部向下查找i 如果查找操作遇到了一個含有i的節(jié)點x 就在x處進行splay操作 插入 i 用i值進行分割操作 原樹割成兩棵子樹 新建i的結點 左右孩子為割出的兩棵子樹 刪除 i 先查找操作 再將根結點的兩棵子樹合并合并 左子樹小于右子樹 先將左子樹最大點splay到根 此時右子樹為空 直接將原先的右子樹掛過去便可 分割 i 直接找到相應結點x splay上去 割開便可 十一 Splay 區(qū)間操作 比如我們要提取區(qū)間 a b 那么我們將a前面一個數(shù)對應的結點轉到樹根 將b后面一個結點對應的結點轉到樹根的右邊 那么根右邊的左子樹就對應了區(qū)間 a b 原因很簡單 將a前面一個數(shù)對應的結點轉到樹根后 a及a后面的數(shù)就在根的右子樹上 然后又將b后面一個結點對應的結點轉到樹根的右邊 那么 a b 這個區(qū)間就是下圖中B所示的子樹 十二 樹鏈剖分 如何在一棵樹上進行路徑的修改 求極值 求和回到我們分塊算法的思考過程中 用空間去換取時間 將某些信息 捆綁 起來 樹鏈 就是樹上的路徑 剖分 就是把路徑分類為重鏈和輕鏈 記siz v 表示以v為根的子樹的節(jié)點數(shù) dep v 表示v的深度 根深度為1 top v 表示v所在的鏈的頂端節(jié)點 fa v 表示v的父親 son v 表示與v在同一重鏈上的v的兒子節(jié)點 姑且稱為重兒子 w v 表示v與其父親節(jié)點的連邊 姑且稱為v的父邊 在線段樹中的位置 只要把這些東西求出來 就能用O logn 的時間完成原問題中的操作 十二 樹鏈剖分 重兒子 siz u 為v的子節(jié)點中siz值最大的 那么u就是v的重兒子 輕兒子 v的其它子節(jié)點 重邊 點v與其重兒子的連邊 輕邊 點v與其輕兒子的連邊 重鏈 由重邊連成的路徑 輕鏈 輕邊 十二 樹鏈剖分 dfs 1 把fa dep siz son求出來 比較簡單 略過 dfs 2 對于v 當son v 存在 即v不是葉子節(jié)點 時 顯然有top son v top v 線段樹中 v的重邊應當在v的父邊的后面 記w son v totw 1 totw表示最后加入的一條邊在線段樹中的位置 此時 為了使一條重鏈各邊在線段樹中連續(xù)分布 應當進行dfs 2 son v 對于v的各個輕兒子u 顯然有top u u 并且w u totw 1 進行dfs 2過程 這就求出了top和w 將樹中各邊的權值在線段樹中更新 建鏈和建線段樹的過程就完成了 十二 樹鏈剖分 記f1 top u f2 top v 當要修改11到10的路徑時 第一次迭代 u 11 v 10 f1 2 f2 10 此時dep f1 dep f2 修改線段樹中10 11號點 u 2 f1 2 第三次迭代 dep f1 dep f2 修改線段樹中9號點 u 1 f1 1 第四次迭代 f1 f2且u v 修改結束 十三 LinkCutTree 樹鏈剖分中重輕鏈的分割方法使得樹的形態(tài)不能發(fā)生改變 否則我們只能重構整個線段樹 這個對于時間復雜度是災難性的 LCT 樹鏈剖分 splayLCT是把樹分解成多個樹鏈 并且把每條樹鏈都分別儲存到一顆splay中 當我們需要對一顆樹上的路徑進行操作的時候 利用splay進行分離與合并 把這條樹上的路徑儲存到同一棵splay中 然后再操作這顆splay就行了 十三 LinkCutTree 在這顆splay中 離根節(jié)點近的邊被儲存到splay的左邊 離根節(jié)點較遠的被儲存到右邊 splaytree是以deep作為關鍵字排序的 十三 LinkCutTree 原樹對應的輔助樹 splay樹 十三 LinkCutTree ACCESS操作是Link CutTrees的所有操作的基礎 假設調用了過程ACCESS v 那么從點v到根結點的路徑就成為一條新的PreferredPath 如果執(zhí)行了一個點的access操作 那么從根節(jié)點到這個點路徑上的所有的點就會變?yōu)槠煤⒆?所有的邊就會變?yōu)槠眠?這條路徑也就變?yōu)橐粭l偏好路徑 同時 從根節(jié)點到該節(jié)點的這條路徑就被儲存到了li