高級(jí)數(shù)據(jù)結(jié)構(gòu)

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