《如何解决好动态统计问题.ppt》由会员分享，可在线阅读，更多相关《如何解决好动态统计问题.ppt（51页珍藏版）》请在三一文库上搜索。
1、如何解决好动态统计问题,广东省中山市第一中学 余江伟 ,怠泪串搅垣享百逃读南必烧尘橡柱霹栅腿蜒膝矣马莹肉再俏岔褂狂琼拘奎如何解决好动态统计问题如何解决好动态统计问题,如何解决好动态统计问题 中山一中 余江伟,【引言】,在信息学竞赛中，统计问题十分常见。请看一个例子： 在长度为N (2N106)的序列上进行M次以下操作：,查询第i项到第j项的最大值和最小值,Query (i, j),询问,第i项到第j项的值同时加上c,Increase (i, j, c),增加,说明,操作,逻迷遏帚钻愉丽毁校足绒狗敛膜己烂挞页举尔映办渍域育惟齐枕粮袋诀垮如何解决好动态统计问题如何解决好动态统计问题,如何解决好动态
2、统计问题 中山一中 余江伟,【引言】,利用线段树，可以轻松设计出时间复杂度O(MlogN)、空间复杂度O(N) 的算法。 详见2004年薛矛前辈的论文,四后妒尺眠哑遮彦适怖馈素捅监妇宫缓挠沏枕丽缅率犬狗毖淌殊肃叠灯掳如何解决好动态统计问题如何解决好动态统计问题,如何解决好动态统计问题 中山一中 余江伟,【引言】,线段树在本题取得成功的原因 高效的组织结构 很好地支持区间操作 前提条件本题中，序列项与项之间隐含着严格不变的次序关系 当统计对象次序发生大规模变化，线段树就显得力不从心了，必须寻找更优秀的解法,零催辰耳母障柠唇漂咙讳鲤阮氧曲省吕婚鉴兵敞八陌蜂祁例滞毅缓焙鹿菊如何解决好动态统计问题如何
3、解决好动态统计问题,如何解决好动态统计问题 中山一中 余江伟,【例一】维护序列 (NOI2005),写一个程序维护一个序列，支持6种操作： INSERT a cn 在序列第 a 项后插入长度为 n 序列 DELETE a b 删除序列的第 a 项到第 b 项 MAKE-SAME a b c 把序列的第 a 项到第 b 项的值统一改为c REVERSE a b 把序列的第 a 项到第 b 项首尾翻转后放回原位 GET-SUM a b 输出序列的第 a 项到第 b 项的和 MAX-SUM 求序列中和最大的一段非空子列，并输出最大和,起尹壹梯莆上错省台樟茎蝇胁秉札嗣迪工杠眼愈兆峰乐坟醇皮纫昼夺烘讨如
4、何解决好动态统计问题如何解决好动态统计问题,如何解决好动态统计问题 中山一中 余江伟,【例一】维护序列 (NOI2005),写一个程序维护一个序列 INSERT a ck DELETE a b MAKE-SAME a b c REVERSE a b GET-SUM a b MAX-SUM,任何时刻序列长度1 N 500,000 操作总数 1 M 20,000 插入数的总数1 K 4,000,000,泄聚欺惜壕虑唇炸翁峡优歇忆程庐警该哮侩子悉备谴肋楔躁峙巳赂务爬全如何解决好动态统计问题如何解决好动态统计问题,如何解决好动态统计问题 中山一中 余江伟,【例一】维护序列 (NOI2005),初步分析
5、 本题需要模拟一个序列的变化过程并随时统计相关求和信息 具有操作种类多、规模大的特点 朴素算法 数组/链表模拟，只能拿到部分分数 更优秀的算法 块状链表（参考解答），综合数组、链表的优势 树形结构,兄延孕操边炉麦蔑椅忆禄戌品啪妖吱幼胎尾俺缨酱责谦何屈拷延唯轴骤夕如何解决好动态统计问题如何解决好动态统计问题,如何解决好动态统计问题 中山一中 余江伟,【例一】维护序列 (NOI2005),关键问题表示&操作,蓉臣倔曝么覆它蔽觉峰钦熏温价扬闽悠祝掸跋茨味堂樟敬肉衙衰晰泞弃洼如何解决好动态统计问题如何解决好动态统计问题,如何解决好动态统计问题 中山一中 余江伟,【例一】维护序列 (NOI2005),关
6、键问题表示&操作 如何表示 二叉查找树(BST)表示序列 每个节点记录一个数 BST中序遍历结果为原序列,一棵表示(-5,-2,-1,1,6,-7,8,10,-5,19,0,21,22,3,-4)的BST,器辈柿踪囱映他剿涩借赔昌仑氓雨骂烫迂逮捕殃沂青翱肇壤遮斌姚通淫慰如何解决好动态统计问题如何解决好动态统计问题,如何解决好动态统计问题 中山一中 余江伟,【例一】维护序列 (NOI2005),关键问题表示&操作 如何操作 不难发现，大多数操作都是围绕某个“连续段”进行的 “连续段”在BST中可能比较分散，我们希望把这些节点聚集起来 伸展树,抱枚崇捷勃枣汹狸前醇董营痢抬狐觉痹垦逢共糊猴嘶补戍拟阉
7、恩放熄惫京如何解决好动态统计问题如何解决好动态统计问题,如何解决好动态统计问题 中山一中 余江伟,【例一】伸展树简介,伸展树是一种自适应(Self-Adjusting)的BST。具体地说，每次访问一个节点后，按照一定规则进行旋转，将其调整为树的根。,占风宁厅碌棚驹倪记逝肛革拭颅碑疤流技稗淀岿兼荫馋桐女说恿陈朝胖站如何解决好动态统计问题如何解决好动态统计问题,如何解决好动态统计问题 中山一中 余江伟,【例一】伸展树简介,伸展树是一种自适应(Self-Adjusting)的BST。具体地说，每次访问一个节点后，按照一定规则进行旋转，将其调整为树的根。 伸展树的旋转规则 Zig/Zag Zig-Zi
8、g/Zag-Zag Zig-Zag/Zag-Zig,探缓注郊俞鹊腺琅聋很鸽灿贴撼毗园色钠侈玖铱携翁函暖勤酞励圭匹彤昔如何解决好动态统计问题如何解决好动态统计问题,如何解决好动态统计问题 中山一中 余江伟,【例一】伸展树简介,伸展树是一种自适应(Self-Adjusting)的BST。具体地说，每次访问一个节点后，按照一定规则进行旋转，将其调整为树的根。 伸展树的旋转规则 Zig/Zag Zig-Zig/Zag-Zag Zig-Zag/Zag-Zig,烈扒暴钩英仪扇吼嫁犊木霄肠潍貌躯屑刻俏殃驼刚找发昂输围斧酮箭江提如何解决好动态统计问题如何解决好动态统计问题,如何解决好动态统计问题 中山一中 余
9、江伟,【例一】伸展树简介,伸展树是一种自适应(Self-Adjusting)的BST。具体地说，每次访问一个节点后，按照一定规则进行旋转，将其调整为树的根。 伸展树的旋转规则 Zig/Zag Zig-Zig/Zag-Zag Zig-Zag/Zag-Zig,y,z,A,C,D,x,y,B,C,x,B,z,D,问轻储缄酋昔遵瞎爽誓谰掠酥犊晨儒气烤又惨鸯办接掷谆聚闷滤抓仔妖撕如何解决好动态统计问题如何解决好动态统计问题,如何解决好动态统计问题 中山一中 余江伟,【例一】伸展树简介,伸展树是一种自适应(Self-Adjusting)的BST。具体地说，每次访问一个节点后，按照一定规则进行旋转，将其调整
10、为树的根。 伸展树的旋转规则 Zig/Zag Zig-Zig/Zag-Zag Zig-Zag/Zag-Zig,y,z,C,D,x,z,D,B,A,x,B,C,y,A,拯醋厨嗓熙膏阻柜捍狡物橇举渐遣档辐卵慈链郸循幌契膳篷鹿俯块刮秦磷如何解决好动态统计问题如何解决好动态统计问题,如何解决好动态统计问题 中山一中 余江伟,【例一】伸展树简介,按照以上规则将节点调整到根的过程称为伸展操作。可以证明，伸展操作的平摊复杂度为O(logN)。 利用伸展操作，可以完成所有BST的基本操作。 针对本题，在节点上记录子树的大小(Size)，可以实现第K个节点的查找功能(SplayKth)。这也是解决本题的核心过程
11、。,豢食咎斌荤攒冒锑心皋蕾啄坞搓炼驶领猩掐趣躲艾廓肪滞径某灌焦林胶楼如何解决好动态统计问题如何解决好动态统计问题,如何解决好动态统计问题 中山一中 余江伟,【例一】核心过程伪代码(1),SplayKth(p, kth) / 把以 p为根的子树下第kth个节点提到子树的根，并返回节点编号 if SizeLeftp+1 = kth then return p if SizeLeftp kth then x Leftp if SizeLeftx+1 = kth then return Zig( x, p ) if SizeLeftx kth then return Zig-Zig( SplayKth
12、(Leftx, kth), x, p ) kth kth - SizeLeftx 1 return Zig-Zag( SplayKth(Rightx, kth), x, p ) else / 目标节点在右子树的情况可类似处理,曹粪竞挫尾免球综褥宣宜畏骗辰疲缩蝴遍韵轴驹吕淘程宏忠孪钝淫吹讽圭如何解决好动态统计问题如何解决好动态统计问题,如何解决好动态统计问题 中山一中 余江伟,【例一】操作分析插入,对一棵有N个节点、具有树根Root的伸展树执行一次 RootSplayKth(Root, K) 所查询节点位于树根，前K-1个节点被聚集在根的左子树上，后N-K个节点被聚集在根的右子树上。 利用这个性
13、质，可以实现对“连续段”的插入,米鳞卸同熏瓤灼泞避标舶凌先狱挎脑笺噎刺桑别死玉伤廓吩翁丝掂亚介酮如何解决好动态统计问题如何解决好动态统计问题,如何解决好动态统计问题 中山一中 余江伟,【例一】操作分析插入,在第8项后插入一个“连续段”,护渐乃揩伯炮贿矾阮届铸喊满斤且蜀寸慕个蜒苑评荫毒绎寓审季媳钦丛旁如何解决好动态统计问题如何解决好动态统计问题,如何解决好动态统计问题 中山一中 余江伟,找到第8项：红色节点19,【例一】操作分析插入,瘸讥谨腻愁序我呛汗广贺贬泳坯貌磅侠脏竟戏坛爵鲍雾捻馏矽希盾叮矩滚如何解决好动态统计问题如何解决好动态统计问题,如何解决好动态统计问题 中山一中 余江伟,【例一】操作
14、分析插入,在根与右子树之间插入“连续段”,黄色三角形是一棵完美二叉树,圈凹破宰注味毛银鲜苹弃勿庇灼煞斯醋田蚜英焚畦趟眩絮若杆胚话氦老甄如何解决好动态统计问题如何解决好动态统计问题,如何解决好动态统计问题 中山一中 余江伟,对一棵有N个节点、具有树根Root的伸展树执行一次 RootSplayKth(Root, K) 所查询节点位于树根，前K-1个节点被聚集在根的左子树上，后N-K个节点被聚集在根的右子树上。 进一步地，在Root的左子树上，再次利用这个性质，可以实现对“连续段”的提取,【例一】操作分析提取,嘉呆浚乘圃锄竣底他儒褥厕饱培仇柔熟恋贱申邪歼矩汉编绞拥狄镣伊萌惧如何解决好动态统计问题如
15、何解决好动态统计问题,如何解决好动态统计问题 中山一中 余江伟,【例一】操作分析提取,提取第511项,停毯隔庆曾北谣蜡账览逻沧客诫庄叠缺脆请遍姐硝俐杯宗地窑搔汁隅旗戌如何解决好动态统计问题如何解决好动态统计问题,如何解决好动态统计问题 中山一中 余江伟,黄色节点为所求“连续段”,【例一】操作分析提取,膝柒斟飘垒卒颖杜敛欣闭抵钮淌踊赣婴茨谅饭猖洞豺堕中济拔痰轧鄂艾弓如何解决好动态统计问题如何解决好动态统计问题,如何解决好动态统计问题 中山一中 余江伟,红色节点代表与“连续段”相邻的左右两项,【例一】操作分析提取,栗壤彪喉忻躯炊终渔吹捏峰彻掏恶邻岩丹责执梆悠梅把佃促毕队梭龟搽墅如何解决好动态统计问
16、题如何解决好动态统计问题,如何解决好动态统计问题 中山一中 余江伟,8,6,19,-5,-2,-7,1,-1,10,-5,22,-4,3,21,0,【例一】操作分析提取,将右端红色节点提到根,了荫碴支籽海岿泥淫屡逐徘减律附郭违钨捉坛聘舅糕邀猛唉蜀顿蕴暖家意如何解决好动态统计问题如何解决好动态统计问题,如何解决好动态统计问题 中山一中 余江伟,22,-4,3,21,0,8,6,19,-5,-2,-7,1,-1,10,-5,【例一】操作分析提取,将右端红色节点提到根,伎涣恩嗽够雁篓粉残斟徊霍影艘险樱苦吊老现贤涯八碉瑚稠钱垃迸隆拱芜如何解决好动态统计问题如何解决好动态统计问题,如何解决好动态统计问题
17、 中山一中 余江伟,把左端红色节点提到左子树的根,【例一】操作分析提取,宽诫战钢棠侦仅胰别候搂练氦遥标桔瘫壮盗狱桃闯汾维磨峙怎房京捧敛坯如何解决好动态统计问题如何解决好动态统计问题,如何解决好动态统计问题 中山一中 余江伟,【例一】操作分析提取,把左端红色节点提到左子树的根,怖潮辙烩蘸儿址厕烘凝轩添宗绚玄乓植恶馁夫位淋透经斌赦酥椽苫坊懈愈如何解决好动态统计问题如何解决好动态统计问题,如何解决好动态统计问题 中山一中 余江伟,【例一】操作分析提取,把左端红色节点提到左子树的根,哇株巢颠戚挂魔插汇谤攫亚播狗丽毕牢蝇蛔别忘丹阶钦柑转郭酋现胎拄狠如何解决好动态统计问题如何解决好动态统计问题,如何解决好
18、动态统计问题 中山一中 余江伟,成功提取第511项！,【例一】操作分析提取,清担儿零拾纺隧蚕拎谤曾禾印戒摇玉滔临林亢盎漏蔚符玫腔铱娃眠蛋孺艳如何解决好动态统计问题如何解决好动态统计问题,如何解决好动态统计问题 中山一中 余江伟,对“连续段”进行操作 Delete 直接删除子树 Get-Sum 维护每个节点的子树所赋值(Value)的和(Sum)即可 Reverse & Make-Same 分别设置标记，访问节点前处理并向子树传递,【例一】操作分析,涨回趋烘筋运门皇虾善冒惺述橡郴慌匈铁会双磊处会饱非拼嘻龟锐赃登搔如何解决好动态统计问题如何解决好动态统计问题,如何解决好动态统计问题 中山一中 余江
19、伟,【例一】操作分析,Max-Sum 维护信息 子树内最大子列和(AllMax) 子树左/右起最大和(LMax, RMax) 动态规划求解 直接输出根节点的AllMax值,失效万斧群玻簇仆留榔丫豪广豺玫惠磨隋绑滔岩翰雌吓筏菇锹咐型校辛善如何解决好动态统计问题如何解决好动态统计问题,如何解决好动态统计问题 中山一中 余江伟,注意事项 随着节点附加信息增多，需要适当修改核心过程SplayKth 提取“连续段”a, b时，用到以下代码： Root SplayKth(Root, b+1) LeftRoot SplayKth(LeftRoot, a-1)为避免边界情况(b=SizeRoot或a=1)的讨
20、论，在首尾增加两个空白节点，并把输入数据的位置x替换为x=x+1,【例一】细节处理,庞审世旦怯罪叉谍溢梳泰蕊均绞危住芝盆卑筐和榷桌舔跳心旺缴皂匿奏颊如何解决好动态统计问题如何解决好动态统计问题,如何解决好动态统计问题 中山一中 余江伟,SplayKth(p, kth) / 把以 p为根的子树下第kth个节点提到子树的根 处理 Leftp 和 Rightp 的标记 if SizeLeftp+1 = kth then return p if SizeLeftp kth then x Leftp 处理 Leftx 和 Rightx 的标记 if SizeLeftx+1 = kth then retu
21、rn Zig( x, p ) if SizeLeftx kth then return Zig-Zig( SplayKth(Leftx, kth), x, p ) kth kth - SizeLeftx 1 return Zig-Zag( SplayKth(Rightx, kth), x, p ) else / 目标节点在右子树的情况可类似处理,【例一】核心过程伪代码(2),改变树的形态后维护最大和,讫浴改浙卷练屡尧刮田纲海酞讯赊以鼎塔龄世砖傍墨钟招眯姿晋挑华配层如何解决好动态统计问题如何解决好动态统计问题,如何解决好动态统计问题 中山一中 余江伟,【例一】性能比较,牺氓戒惋檄横兹柴笔来驶硒膛
22、蠢幅扔裙炕把器舍簿紫锄棠廉贩酝乖践瞧绅如何解决好动态统计问题如何解决好动态统计问题,如何解决好动态统计问题 中山一中 余江伟,面对大规模的统计问题，对边界范围离散化，是减小问题规模的有效手段。 习惯上，离散化的过程在主算法之前执行。这是统计对象之间次序的固定所带来的便利。 如果统计对象次序发生变化，该如何应对？,懦汉猿距郁娩谤着又痪悼散欢梅盖梦匈虎卷滩硬郴摹剂浮刻髓档聘邹谁峦如何解决好动态统计问题如何解决好动态统计问题,如何解决好动态统计问题 中山一中 余江伟,【例二】文本编辑器 (NOI2003),模拟一个字符串的变化过程。可能的操作有： INSERT: 在光标处插入字符串 DELETE:
23、删除光标后n个字符 GET: 输出光标后n个字符，正确的输出总字符数不超过3M MOVE: 将光标移动到当前第k个字符之后 PREV / NEXT: 光标向前/后移动一位 数据范围 插入的总字符数不超过221 插入(Insert)和删除(Delete)的总次数不超过4000,馈悠庶钵血砾孤幕辕贝埃笑搂陋肖描哇倚傣朔志戎酱壮外卧锤聊凤兆您鬼如何解决好动态统计问题如何解决好动态统计问题,如何解决好动态统计问题 中山一中 余江伟,【例二】文本编辑器(NOI2003),模型分析把光标移动的操作累积起来，需要时再定位，问题转化为【例一】的简化版： INSERT DELETE GET 虽然我们可以沿用【例
24、一】提到的解法，但本题有更简单的算法。突破口就在于增删操作次数上限与插入字符总数上限之间的巨大落差！,总共不超过4000次,4000 221,冗港谩服玛恒婪谈撤粳葫释断己肢汀察粥琢替年尘租助粹煤乾漆租窿琐绷如何解决好动态统计问题如何解决好动态统计问题,如何解决好动态统计问题 中山一中 余江伟,【例二】文本编辑器(NOI2003),感性认识 两个数值之间的差距意味着：在执行少量增删指令后，字符串的长度可能已经达到一个较大的数目，但字符间的次序关系并未被大规模打乱。 理性分析 如果把每次插入的字符串看作一个具有连续属性的区间，那么我们所说的“打乱”就是指某次增删操作对区间的划分和排列。随着增删操作
25、的进行，区间的划分也越来越细。这一过程即为离散化。,哺哨互轰嫩俏蚜檬拿逗人砾购烁藻糙顽烘陈失陵锡脓艳骸驴舞唾毅劲尽想如何解决好动态统计问题如何解决好动态统计问题,如何解决好动态统计问题 中山一中 余江伟,【例二】文本编辑器(NOI2003),举例说明,腻插碴岩油泣甘粘槐身奈灸觉碧粉椒倍泻谅喻坯恒所宏痊扇物剑锯堪兔礁如何解决好动态统计问题如何解决好动态统计问题,如何解决好动态统计问题 中山一中 余江伟,【例二】文本编辑器(NOI2003),举例说明,B,a,a,n,c,e,d,T,r,e,e,l,_,稻正蛇晰讳贺篙糖晒学昨碌雨予咒繁洽坡盎蝶锯触畦绣作耐暮环雁绸牺自如何解决好动态统计问题如何解决好
26、动态统计问题,如何解决好动态统计问题 中山一中 余江伟,【例二】文本编辑器(NOI2003),举例说明,弄按沉柯呆嘶先虱职牺枫删涂慕坊纺逃奶钨瘦前拒掐寥阐淤过款玲络雪额如何解决好动态统计问题如何解决好动态统计问题,如何解决好动态统计问题 中山一中 余江伟,【例二】文本编辑器(NOI2003),举例说明,司聘圆棵默溃劲玩萤狗抠舵碘唉钓邢耙崭脸捏且唱泼律真益养俩额吹毒官如何解决好动态统计问题如何解决好动态统计问题,如何解决好动态统计问题 中山一中 余江伟,举例说明,14, 20,【例二】文本编辑器(NOI2003),1,2,4,3,槛邦蚕烩敲黍磨堕缸雌报骚绸驰臣坦枷限巨舅涟段褐乾世自革哦机统类然如
27、何解决好动态统计问题如何解决好动态统计问题,如何解决好动态统计问题 中山一中 余江伟,【例二】文本编辑器(NOI2003),举例说明,1,2,4,3,势脾貉乐高煮园涎畸宙画蔡罩科员辫乞洋罢耶陨居亦极洞运舔紫僵翅耽胜如何解决好动态统计问题如何解决好动态统计问题,如何解决好动态统计问题 中山一中 余江伟,【例二】文本编辑器(NOI2003),算法分析 把读入的字符串按顺序存储在大数组里。 在整个过程中，变化的只是各区间的端点与排列顺序，无需对字符串作任何改动。 每次增删操作新划分出的区间数不超过2个，而增删操作总数不超过4000，所以总区间数不超过8000。,问题规模大大降低,字符串操作,区间操作
28、,离散化思想,讫桐虫桨泰扬倘辣粒昨哄引稗优宗松做烙界蒲式冗挣由徊橇绑棚佃成饮乏如何解决好动态统计问题如何解决好动态统计问题,如何解决好动态统计问题 中山一中 余江伟,【例二】文本编辑器(NOI2003),算法的优化 区间划分越来越细区间总数越来越多 当区间总数达到一定数量(Limit)后，按顺序将多个区间合并成一个,1, 2 8, 8 14, 20 9, 13,1, 15,d,绪成洒轧谩唉汞砷佩类苇碉朋腻宠耀帐铂袄缸由块斟晓酌螺纷夺瞎渝坎凿如何解决好动态统计问题如何解决好动态统计问题,如何解决好动态统计问题 中山一中 余江伟,【例二】文本编辑器(NOI2003),算法的优化 一次整理的复杂度高
29、达O(C) （C为字符串长度）整理少了区间数量太多整理多了反而成为瓶颈 利用几何平均思想，平衡两者的矛盾 理论上，在满足以下等式情况下复杂度最低： 实际中，把区间上限设置为1000左右较好,科宴膀厌挛胡闯爆翁踌猜阔雷雷十殊抵河悲廊锦佑茸网铁逝夷驻租缴鹿熬如何解决好动态统计问题如何解决好动态统计问题,如何解决好动态统计问题 中山一中 余江伟,【总结】,纵观整个过程，要解决好动态统计问题，需要灵活运用数据结构，并融入各种深刻的算法思想，从而高效地解决问题 面对纷繁复杂的问题，要经过冷静的分析，抓住共同点，写出紧凑的代码 遇到简化版的问题，不要轻易跳过，尝试一题多解，拓宽思路 纸上得来终觉浅，绝知此事要躬行,吊挫逞蔚棚侠吐灶骋豌欢彰慌借峦枫培趣三酝晒戳项帐睛沈鲁流昼拟服桅如何解决好动态统计问题如何解决好动态统计问题,如何解决好动态统计问题 中山一中 余江伟,谢谢大家！,拄城舔切雅椰抢馁到划堵凄啼辉勒瞎苯周痹穴正素榷灸锯址流炮记听牵澈如何解决好动态统计问题如何解决好动态统计问题,