數(shù)據(jù)結(jié)構(gòu)并查集教學(xué)資料ppt電子教案課件.ppt

并查集 回顧 并查集 union findset 是一種用于分離集合操作的抽象數(shù)據(jù)類型 它所處理的是 集合 之間的關(guān)系設(shè)想需要對(duì)不相交集合 disjoinset 進(jìn)行兩種操作 1 檢查某元素屬于哪個(gè)集合 2 合并兩個(gè)集合 執(zhí)行n次合并和m m n 次查詢 并查集可以實(shí)現(xiàn)o 1 的平攤復(fù)雜度 并查集的實(shí)現(xiàn) 1 用一棵樹(shù)來(lái)代表一個(gè)集合 集合里的每個(gè)元素都是樹(shù)的一個(gè)節(jié)點(diǎn) 2 用樹(shù)根來(lái)唯一標(biāo)示這棵樹(shù) 這個(gè)集合 3 那個(gè)元素作為根無(wú)所謂 只要屬于同一集合的根相同4 所有的這些集合構(gòu)成了一個(gè)森林 路徑壓縮 找到根節(jié)點(diǎn)之后 將路徑上的節(jié)點(diǎn)都直接鏈接到根節(jié)點(diǎn) 這樣在下次查找時(shí) 便可以減少查找次數(shù) 這一優(yōu)化稱為路徑壓縮 并查集的拓展 記錄更多的信息比如 兩個(gè)結(jié)點(diǎn)的相對(duì)關(guān)系信息的表示 表示并查集的森林的邊帶上權(quán) 偏移量 食物鏈 動(dòng)物王國(guó)中有三類動(dòng)物a b c 這三類動(dòng)物的食物鏈構(gòu)成了有趣的環(huán)形 a吃b b吃c c吃a 現(xiàn)有n個(gè)動(dòng)物 以1 n編號(hào) 每個(gè)動(dòng)物都是a b c中的一種 但是我們并不知道它到底是哪一種 有人用兩種說(shuō)法對(duì)這n個(gè)動(dòng)物所構(gòu)成的食物鏈關(guān)系進(jìn)行描述 第一種說(shuō)法是 1xy 表示x和y是同類 第二種說(shuō)法是 2xy 表示x吃y 此人對(duì)n個(gè)動(dòng)物 用上述兩種說(shuō)法 一句接一句地說(shuō)出k句話 這k句話有的是真的 有的是假的 當(dāng)一句話滿足下列三條之一時(shí) 這句話就是假話 否則就是真話 1 當(dāng)前的話與前面的某些真的話沖突 就是假話 2 當(dāng)前的話中x或y比n大 就是假話 3 當(dāng)前的話表示x吃x 就是假話 你的任務(wù)是根據(jù)給定的n 1 n 50 000 和k句話 0 k 100 000 輸出假話的總數(shù) 合并同類 查找兩種動(dòng)物是否屬于同一個(gè)集合 表示它們是同類 那x吃y怎么表示 3類動(dòng)物3個(gè)集合 怎么確定xy是哪一類 我們用偏移量offset a b 表示a和b的關(guān)系 offset a b 0表示a和b是同類 offset a b 1表示a吃b offset a b 2表示b吃a 那么對(duì)任意種類東西c 顯然offset a b offset a c offset c b 3這個(gè)關(guān)系式表明 a和b的關(guān)系可以通過(guò)a和根的關(guān)系以及b和根的關(guān)系推斷出來(lái) 由上述結(jié)論得 同一集合內(nèi)任意元素關(guān)系可推出 即關(guān)系已知 將確定關(guān)系的兩個(gè)動(dòng)物 合并為一個(gè)集合若兩個(gè)動(dòng)物不在同一個(gè)集合 那么關(guān)系未知 偏移量的更新 路徑壓縮 offset a 表示a與其父節(jié)點(diǎn)的關(guān)系設(shè)原fa a p 路徑壓縮使fa a rootoffset a root offset a p offset p root 3即offset a offset a offset p 3 線段樹(shù) 部分引用pku 郭煒的ppt 線段樹(shù) 樹(shù) 是一棵樹(shù) 而且是一棵二叉樹(shù) 線段 樹(shù)上的每個(gè)節(jié)點(diǎn)對(duì)應(yīng)于一個(gè)區(qū)間 同一層的節(jié)點(diǎn)所代表的區(qū)間 相互不會(huì)重疊 同一層節(jié)點(diǎn)所代表的區(qū)間 加起來(lái)是個(gè)連續(xù)的區(qū)間 葉子節(jié)點(diǎn)的區(qū)間是單位長(zhǎng)度 不能再分了 線段樹(shù)是一棵二叉樹(shù) 樹(shù)中的每一個(gè)結(jié)點(diǎn)表示了一個(gè)區(qū)間 a b a b通常是整數(shù) 每一個(gè)葉子節(jié)點(diǎn)表示了一個(gè)單位區(qū)間 對(duì)于每一個(gè)非葉結(jié)點(diǎn)所表示的結(jié)點(diǎn) a b 其左兒子表示的區(qū)間為 a a b 2 右兒子表示的區(qū)間為 a b 2 1 b 除法去尾取整 區(qū)間 1 9 的線段樹(shù) 線段樹(shù)的平分構(gòu)造 實(shí)際上是用了二分的方法 若根節(jié)點(diǎn)對(duì)應(yīng)的區(qū)間是 a b 那么它的深度為log2 b a 1 1 向上取整 葉子節(jié)點(diǎn)的數(shù)目和根節(jié)點(diǎn)表示區(qū)間的長(zhǎng)度相同 區(qū)間分解 分解的規(guī)則就是 如果有某個(gè)節(jié)點(diǎn)代表的區(qū)間 完全屬于待分解區(qū)間 則該節(jié)點(diǎn)為 終止 節(jié)點(diǎn) 不再繼續(xù)往下分解所有 終止 節(jié)點(diǎn)所代表的區(qū)間都不重疊 且加在一起就恰好等于整個(gè)待分解區(qū)間 區(qū)間 1 9 的線段樹(shù)上 區(qū)間 2 8 的分解 區(qū)間分解的時(shí)候 每層最多2個(gè) 終止節(jié)點(diǎn) 所以終止節(jié)點(diǎn)總數(shù)也是log n 量級(jí)的 x代表終止節(jié)點(diǎn) 上述情況不可能發(fā)生 線段樹(shù)的特征 1 線段樹(shù)的深度不超過(guò)log2 n 1 向上取整 n是根節(jié)點(diǎn)對(duì)應(yīng)區(qū)間的長(zhǎng)度 2 線段樹(shù)上 任意一個(gè)區(qū)間被分解后得到的 終止節(jié)點(diǎn) 數(shù)目都是log n 量級(jí) 線段樹(shù)上更新葉子節(jié)點(diǎn)和進(jìn)行區(qū)間分解時(shí)間復(fù)雜度都是o log n 的這些結(jié)論為線段樹(shù)能在o log n 的時(shí)間內(nèi)完成一個(gè)區(qū)間的建樹(shù) 插入數(shù)據(jù) 更新數(shù)據(jù) 查找 統(tǒng)計(jì)等工作 提供了理論依據(jù) 敵兵布陣 一個(gè)正整數(shù)n n 50000 表示敵人有n個(gè)工兵營(yíng)地 接下來(lái)有n個(gè)正整數(shù) 第i個(gè)正整數(shù)ai代表第i個(gè)工兵營(yíng)地里開(kāi)始時(shí)有ai個(gè)人 1 ai 50 接下來(lái)每行有一條命令 命令有4種形式 1 addij i和j為正整數(shù) 表示第i個(gè)營(yíng)地增加j個(gè)人 j不超過(guò)30 2 subij i和j為正整數(shù) 表示第i個(gè)營(yíng)地減少j個(gè)人 j不超過(guò)30 3 queryij i和j為正整數(shù) i j 表示詢問(wèn)第i到第j個(gè)營(yíng)地的總?cè)藬?shù) 每組數(shù)據(jù)最多有40000條命令 建立 點(diǎn)更新 區(qū)間更新 查詢 線段樹(shù)適用于多次查詢用線段樹(shù)解題 關(guān)鍵是要想清楚每個(gè)節(jié)點(diǎn)要存哪些信息 當(dāng)然區(qū)間起終點(diǎn) 以及左右子節(jié)點(diǎn)指針是必須的 以及這些信息如何高效更新 維護(hù) 查詢 不要一更新就更新到葉子節(jié)點(diǎn) 那樣更新效率最壞就可能變成o n 的了 樹(shù)狀數(shù)組 對(duì)于序列a 我們?cè)O(shè)一個(gè)數(shù)組cc i a i 2 k 1 a i k為i在二進(jìn)制下末尾0的個(gè)數(shù)2 k就是i保留最右邊的1 其余位全變0i從1開(kāi)始算 c即為a的樹(shù)狀數(shù)組對(duì)于i 如何求2 k 通常我們用lowbit x 表示x對(duì)應(yīng)的2klowbit x x x c i a i lowbit i 1 a i c1 a1c2 a1 a2c3 a3c4 a1 a2 a3 a4c5 a5c6 a5 a6c7 a7c8 a1 a2 a3 a4 a5 a6 a7 a8 c16 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12 a13 a14 a15 a16 圖示 設(shè)sum k a 1 a 2 a k 則a i a i 1 a j sum j sum i 1 根據(jù)c的構(gòu)成規(guī)律 可以發(fā)現(xiàn)sum k 可以表示為 sum k c n1 c n2 c nm 其中nm kni 1 ni lowbit ni ni lowbit ni 是什么樣子 就是ni的二進(jìn)制去掉最右邊的1k的二進(jìn)制里最多有幾個(gè)1 log2k 向上取整 個(gè)sum k 最多l(xiāng)og2k 向上取整 項(xiàng) 所以本次求和的復(fù)雜度就是log2k 如果a i 更新了 那么以下的幾項(xiàng)都需要更新 c n1 c n2 c nm 其中 n1 i ni 1 ni lowbit ni 同理 總的來(lái)說(shuō)更新一個(gè)元素的時(shí)間 也是logn的 a i 更新 c i 必須更新c i 更新 c i lowbit i 必須更新 c i lowbit i a i lowbit i lowbit i lowbit i 1 a i lowbit i 證明i lowbit i lowbit i lowbit i 1 i 就證明c i lowbit i 要更新lowbit i 顯然比lowbit i lowbit i 要小所以i lowbit i lowbit i lowbit i 1 i 下面要證明 若c i 更新 則對(duì)任何k i k i lowbit i c k 都不需要更新 即c k 不包含a i c k a k lowbit k 1 a k 只要證明k lowbit k 1比i大即可因i k i lowbit i 假設(shè)i的最右邊的1是從右到左從0開(kāi)始數(shù)的第n位 那么i lowbit i 就是將i的低n位全變成1后 再加1 那么k一定是從第n位到最高位都和i相同 但是低n位比