国家集训队2007论文集4.余江伟“如何解决好.ppt

如何解决好动态统计问题;【引言】;【引言】;【引言】;【例一】维护序列 (NOI2005);【例一】维护序列 (NOI2005);【例一】维护序列 (NOI2005);【例一】维护序列 (NOI2005);【例一】维护序列 (NOI2005);【例一】维护序列 (NOI2005);【例一】伸展树简介;【例一】伸展树简介;【例一】伸展树简介;【例一】伸展树简介;【例一】伸展树简介;【例一】伸展树简介;【例一】核心过程伪代码(1);【例一】操作分析——插入;8;8;8;对一棵有N个节点、具有树根Root的伸展树执行一次 Root←SplayKth(Root, K) 所查询节点位于树根，前K-1个节点被聚集在根的左子树上，后N-K个节点被聚集在根的右子树上。 进一步地，在Root的左子树上，再次利用这个性质，可以实现对“连续段”的提取;8;8;8;22;22;10;10;6;10;10;【例一】操作分析;注意事项 随着节点附加信息增多，需要适当修改核心过程SplayKth 提取“连续段”[a, b]时，用到以下代码： Root ← SplayKth(Root, b+1) Left[Root] ← SplayKth(Left[Root], a-1)为避免边界情况(b=Size[Root]或a=1)的讨论，在首尾增加两个空白节点，并把输入数据的位置x替换为x’=x+1 ;SplayKth(p, kth) // 把以 p为根的子树下第kth个节点提到子树的根 处理 Left[p] 和 Right[p] 的标记 if Size[Left[p]]+1 = kth then return p if Size[Left[p]] ≥ kth then x ← Left[p] 处理 Left[x] 和 Right[x] 的标记 if Size[Left[x]]+1 = kth then return Zig( x, p ) if Size[Left[x]] ≥ kth then return Zig-Zig( SplayKth(Left[x], kth), x, p ) kth ← kth - Size[Left[x]] – 1 return Zig-Zag( SplayKth(Right[x], kth), x, p ) else… // 目标节点在右子树的情况可类似处理 ;【例一】性能比较;;【例二】文本编辑器 (NOI2003);【例二】文本编辑器(NOI2003);【例二】文本编辑器(NOI2003);【例二】文本编辑器(NOI2003);【例二】文本编辑器(NOI2003);【例二】文本编辑器(NOI2003);【例二】文本编辑器(NOI2003);举例说明;【例二】文本编辑器(NOI2003);【例二】文本编辑器(NOI2003);【例二】文本编辑器(NOI2003);【例二】文本编辑器(NOI2003);【总结】;谢谢大家！