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

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