如何解決好動(dòng)態(tài)統(tǒng)計(jì)問題(編輯修改稿)
2024-08-14 20:59 本頁面
【文章內(nèi)容簡介】 Root←SplayKth(Root, K) 所查詢節(jié)點(diǎn)位于樹根，前 K1個(gè)節(jié)點(diǎn)被聚集在根的左子樹上，后 NK個(gè)節(jié)點(diǎn)被聚集在根的右子樹上。 ? 進(jìn)一步地，在 Root的左子樹上，再次利用這個(gè)性質(zhì)，可以實(shí)現(xiàn)對(duì)“連續(xù)段”的 提取 【 例一 】 操作分析 —— 提取 如何解決好動(dòng)態(tài)統(tǒng)計(jì)問題 中山一中 余江偉 8 6 19 5 2 7 1 1 10 5 22 4 3 21 0 【 例一 】 操作分析 —— 提取 提取第 5～ 11項(xiàng) 如何解決好動(dòng)態(tài)統(tǒng)計(jì)問題 中山一中 余江偉 8 6 19 5 2 7 1 1 10 5 22 4 3 21 0 黃色節(jié)點(diǎn)為所求“連續(xù)段” 【 例一 】 操作分析 —— 提取 如何解決好動(dòng)態(tài)統(tǒng)計(jì)問題 中山一中 余江偉 8 6 19 5 2 7 1 1 10 5 22 4 3 21 0 紅色節(jié)點(diǎn)代表與“連續(xù)段”相鄰的左右兩項(xiàng) 【 例一 】 操作分析 —— 提取 如何解決好動(dòng)態(tài)統(tǒng)計(jì)問題 中山一中 余江偉 22 4 3 21 0 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 【 例一 】 操作分析 —— 提取 將右端紅色節(jié)點(diǎn)提到根 如何解決好動(dòng)態(tài)統(tǒng)計(jì)問題 中山一中 余江偉 22 4 3 21 0 8 6 19 5 2 7 1 1 10 5 10 5 22 3 4 0 8 6 5 2 7 1 1 19 21 【 例一 】 操作分析 —— 提取 將右端紅色節(jié)點(diǎn)提到根 如何解決好動(dòng)態(tài)統(tǒng)計(jì)問題 中山一中 余江偉 10 5 22 3 4 0 8 6 5 2 7 1 1 19 21 把左端紅色節(jié)點(diǎn)提到左子樹的根 【 例一 】 操作分析 —— 提取 如何解決好動(dòng)態(tài)統(tǒng)計(jì)問題 中山一中 余江偉 10 5 22 3 4 0 8 6 5 2 7 1 1 19 21 6 5 2 7 1 1 10 5 22 3 4 0 8 19 21 【 例一 】 操作分析 —— 提取 把左端紅色節(jié)點(diǎn)提到左子樹的根 如何解決好動(dòng)態(tài)統(tǒng)計(jì)問題 中山一中 余江偉 6 5 2 7 1 1 10 5 22 3 4 0 8 19 21 10 5 0 8 6 2 7 1 1 19 5 22 3 4 21 【 例一 】 操作分析 —— 提取 把左端紅色節(jié)點(diǎn)提到左子樹的根 如何解決好動(dòng)態(tài)統(tǒng)計(jì)問題 中山一中 余江偉 10 5 0 8 6 2 7 1 1 19 5 22 3 4 21 成功提取第 5～ 11項(xiàng)！ 【 例一 】 操作分析 —— 提取 如何解決好動(dòng)態(tài)統(tǒng)計(jì)問題 中山一中 余江偉 10 5 0 8 6 2 7 1 1 19 5 22 3 4 21 ? 對(duì)“連續(xù)段”進(jìn)行操作 ? Delete ? 直接刪除子樹 ? GetSum ? 維護(hù)每個(gè)節(jié)點(diǎn)的子樹所賦值 (Value)的和 (Sum)即可 ? Reverse amp。 MakeSame ? 分別設(shè)置 標(biāo)記 ，訪問節(jié)點(diǎn)前 處理 并向子樹 傳遞 【 例一 】 操作分析 如何解決好動(dòng)態(tài)統(tǒng)計(jì)問題 中山一中 余江偉 【 例一 】 操作分析 ? MaxSum ? 維護(hù)信息 ? 子樹內(nèi)最大子列和(AllMax) ? 子樹左 /右起最大和(LMax, RMax) ? 動(dòng)態(tài)規(guī)劃求解 ? 直接輸出根節(jié)點(diǎn)的AllMax值 8 6 19 5 2 7 1 1 10 5 22 4 3 21 0 如何解決好動(dòng)態(tài)統(tǒng)計(jì)問題 中山一中 余江偉 ? 注意事項(xiàng) ? 隨著節(jié)點(diǎn)附加信息增多，需要適當(dāng)修改核心過程SplayKth ? 提取“連續(xù)段” [a, b]時(shí)，用到以下代碼： Root ← SplayKth(Root, b+1)
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號(hào)-1