如何解決好動態(tài)統(tǒng)計問題-在線瀏覽
2024-08-28 20:59本頁面
【正文】 Zag/ZagZig y z C D x z D B A x B C y A 如何解決好動態(tài)統(tǒng)計問題 中山一中 余江偉 【 例一 】 伸展樹簡介 ? 按照以上規(guī)則將節(jié)點調(diào)整到根的過程稱為 伸展操作 。 ? 利用伸展操作，可以完成所有 BST的基本操作。這也是解決本題的核心過程。 ? 利用這個性質(zhì)，可以實現(xiàn)對“連續(xù)段”的 插入 如何解決好動態(tài)統(tǒng)計問題 中山一中 余江偉 8 6 19 5 2 7 1 1 10 5 22 4 3 21 0 【 例一 】 操作分析 —— 插入 在第 8項后插入一個“連續(xù)段” 如何解決好動態(tài)統(tǒng)計問題 中山一中 余江偉 8 6 19 5 2 7 1 1 10 5 22 4 3 21 0 8 6 19 5 2 7 1 1 10 5 22 4 3 21 0 找到第 8項：紅色節(jié)點 19 【 例一 】 操作分析 —— 插入 如何解決好動態(tài)統(tǒng)計問題 中山一中 余江偉 8 6 19 5 2 7 1 1 10 5 22 4 3 21 0 14 【 例一 】 操作分析 —— 插入 在根與右子樹之間插入“連續(xù)段” 黃色三角形是一棵完美二叉樹 如何解決好動態(tài)統(tǒng)計問題 中山一中 余江偉 ? 對一棵有 N個節(jié)點、具有樹根 Root的伸展樹執(zhí)行一次 Root←SplayKth(Root, K) 所查詢節(jié)點位于樹根，前 K1個節(jié)點被聚集在根的左子樹上，后 NK個節(jié)點被聚集在根的右子樹上。 MakeSame ? 分別設(shè)置 標(biāo)記 ，訪問節(jié)點前 處理 并向子樹 傳遞 【 例一 】 操作分析 如何解決好動態(tài)統(tǒng)計問題 中山一中 余江偉 【 例一 】 操作分析 ? MaxSum ? 維護(hù)信息 ? 子樹內(nèi)最大子列和(AllMax) ? 子樹左 /右起最大和(LMax, RMax) ? 動態(tài)規(guī)劃求解 ? 直接輸出根節(jié)點的AllMax值 8 6 19 5 2 7 1 1 10 5 22 4 3 21 0 如何解決好動態(tài)統(tǒng)計問題 中山一中 余江偉 ? 注意事項 ? 隨著節(jié)點附加信息增多，需要適當(dāng)修改核心過程SplayKth ? 提取“連續(xù)段” [a, b]時，用到以下代碼： Root ← SplayKth(Root, b+1) Left[Root] ← SplayKth(Left[Root], a 1) 為避免邊界情況 (b=Size[Root]或 a=1)的討論，在首尾增加兩個空白節(jié)點，并把輸入數(shù)據(jù)的位置 x替換為 x’=x+1 【 例一 】 細(xì)節(jié)處理 如何解決好動態(tài)統(tǒng)計問題 中山一中 余江偉 SplayKth(p, kth) // 把以 p為根的子樹下第 kth個節(jié)點提到子樹的根 1 處理 Left[p] 和 Right[p] 的標(biāo)記 2 if Size[Left[p]]+1 = kth then return p 3 if Size[Left[p]] ≥ kth 4 then x ← Left[p] 5 處理 Left[x] 和 Right[x] 的標(biāo)記 6 if Size[Left[x]]+1 = kth then return Zig( x, p ) 7 if Size[Left[x]] ≥ kth then 8 return ZigZig( SplayKth(Left[x], kth), x, p ) 9 kth ← kth Size[Left[x]] – 1 10 return ZigZag( SplayKth(Right[x], kth), x, p ) 11 else… // 目標(biāo)節(jié)點在右子樹的情況可類似處理 【 例一 】 核心過程偽代碼 (2) 改變樹的形態(tài) 后維護(hù)最大和 如何解決好動態(tài)統(tǒng)計問題 中山一中 余江偉 【 例一 】 性能比較 012用時( 單位秒)1 2 3 4 5 6 7 8 9 10測試點參考解答(塊狀鏈表)伸展樹如何解決好動態(tài)統(tǒng)計問題 中山一中 余江偉 ?
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號-1