如何解決好動(dòng)態(tài)統(tǒng)計(jì)問(wèn)題-文庫(kù)吧資料
2025-07-24 20:59本頁(yè)面
【正文】 把左端紅色節(jié)點(diǎn)提到左子樹(shù)的根 【 例一 】 操作分析 —— 提取 如何解決好動(dòng)態(tài)統(tǒng)計(jì)問(wèn)題 中山一中 余江偉 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)提到左子樹(shù)的根 如何解決好動(dòng)態(tài)統(tǒng)計(jì)問(wèn)題 中山一中 余江偉 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)提到左子樹(shù)的根 如何解決好動(dòng)態(tài)統(tǒng)計(jì)問(wèn)題 中山一中 余江偉 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ì)問(wèn)題 中山一中 余江偉 10 5 0 8 6 2 7 1 1 19 5 22 3 4 21 ? 對(duì)“連續(xù)段”進(jìn)行操作 ? Delete ? 直接刪除子樹(shù) ? GetSum ? 維護(hù)每個(gè)節(jié)點(diǎn)的子樹(shù)所賦值 (Value)的和 (Sum)即可 ? Reverse amp。 如何解決好動(dòng)態(tài)統(tǒng)計(jì)問(wèn)題 中山一中 余江偉 【 例一 】 核心過(guò)程偽代碼 (1) SplayKth(p, kth) // 把以 p為根的子樹(shù)下第 kth個(gè)節(jié)點(diǎn)提到子樹(shù)的根，并返回節(jié)點(diǎn)編號(hào) 1 if Size[Left[p]]+1 = kth then return p 2 if Size[Left[p]] ≥ kth 3 then x ← Left[p] 4 if Size[Left[x]]+1 = kth then return Zig( x, p ) 5 if Size[Left[x]] ≥ kth then 6 return ZigZig( SplayKth(Left[x], kth), x, p ) 7 kth ← kth Size[Left[x]] – 1 8 return ZigZag( SplayKth(Right[x], kth), x, p ) 9 else… // 目標(biāo)節(jié)點(diǎn)在右子樹(shù)的情況可類(lèi)似處理 如何解決好動(dòng)態(tài)統(tǒng)計(jì)問(wèn)題 中山一中 余江偉 【 例一 】 操作分析 —— 插入 ? 對(duì)一棵有 N個(gè)節(jié)點(diǎn)、具有樹(shù)根 Root的伸展樹(shù)執(zhí)行一次 Root←SplayKth(Root, K) 所查詢(xún)節(jié)點(diǎn)位于樹(shù)根，前 K1個(gè)節(jié)點(diǎn)被聚集在根的左子樹(shù)上，后 NK個(gè)節(jié)點(diǎn)被聚集在根的右子樹(shù)上。 ? 針對(duì)本題，在節(jié)點(diǎn)上記錄子樹(shù)的大小 (Size)，可以實(shí)現(xiàn)第 K個(gè)節(jié)點(diǎn)的查找功能 (SplayKth)?？梢宰C明，伸展操作的平攤復(fù)雜度為O(logN)。具體地說(shuō)，每次訪問(wèn)一個(gè)節(jié)點(diǎn)后，按照一定規(guī)則進(jìn)行旋轉(zhuǎn)，將其調(diào)整為樹(shù)的根。具體地說(shuō)，每次訪問(wèn)一個(gè)節(jié)點(diǎn)后，按照一定規(guī)則進(jìn)行旋轉(zhuǎn)，將其調(diào)整為樹(shù)的根。具體地說(shuō)，每次訪問(wèn)一個(gè)節(jié)點(diǎn)后，按照一定規(guī)則進(jìn)行旋轉(zhuǎn)，將其調(diào)整為樹(shù)的根。具體地說(shuō)，每次訪問(wèn)一個(gè)節(jié)點(diǎn)后，按照一定規(guī)則進(jìn)行旋轉(zhuǎn)，將其調(diào)整為樹(shù)的根。具體地說(shuō)，每次訪問(wèn)一個(gè)節(jié)點(diǎn)后，按照一定規(guī)則進(jìn)行旋轉(zhuǎn)，將其調(diào)整為樹(shù)的根。操作 ? 如何表示 ? 二叉查找樹(shù) (BST)表示序列 ? 每個(gè)節(jié)點(diǎn)記錄一個(gè)數(shù) ? BST中序遍歷結(jié)果為原序列 一棵表示 (5,2,1,1,6,7,8,10,5,19,0,21,22,3,4)的 BST 8 6 19 5 2 7 1 1 10 5 22 4 3 21 0 如何解決好動(dòng)態(tài)統(tǒng)計(jì)問(wèn)題 中山一中 余江偉 【 例一 】 維護(hù)序列 (NOI2022) ? 關(guān)鍵問(wèn)題 —— 表示 amp。 ? 詳見(jiàn) 2022年薛矛前輩的論文 如何解決好動(dòng)態(tài)統(tǒng)計(jì)問(wèn)題 中山一中 余江偉 【 引言 】 ? 線段樹(shù)在本題取得成功的原因 ? 高效的組織結(jié)構(gòu) ? 很好地支持區(qū)間操作 ? 前提條件 —— 本題中，序列項(xiàng)與項(xiàng)之間隱含著嚴(yán)格不變的次序關(guān)系 ? 當(dāng)統(tǒng)計(jì)對(duì)象次序發(fā)生
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號(hào)-1