《如何解决好动态统计问题》由会员分享，可在线阅读，更多相关《如何解决好动态统计问题（51页珍藏版）》请在金锄头文库上搜索。
1、如何解决好动态统计问题 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life, there is hope。有生命必有希望。有生命必有希望【引言】n在信息学竞赛中，统计问题十分常见。请看一个例子：q在长度为N (2N106)的序列上进行M次以下操作：查询第i项到第j项的最大值和最小值Query (i, j)询问第i项到第j项的值同时加上cIncrease (i, j, c)增加说明操作如何解决好动态统计问题中山一中 余江伟【引言】n利用线段树，可以轻松设计出时间复杂度O(MlogN)、空间复杂度O(N) 的算法。 n详见2004
2、年薛矛前辈的论文如何解决好动态统计问题中山一中 余江伟【引言】n线段树在本题取得成功的原因q高效的组织结构q很好地支持区间操作q前提条件前提条件本题中，序列项与项之间隐含本题中，序列项与项之间隐含着严格不变的次序关系着严格不变的次序关系 n当统计对象次序发生大规模变化，线段树就显得力不从心了，必须寻找更优秀的解法如何解决好动态统计问题中山一中 余江伟【例一】维护序列【例一】维护序列 (NOI2005)n写一个程序维护一个序列，支持6种操作：qINSERT a cn n在序列第 a 项后插入长度为 n 序列qDELETE a b n删除序列的第 a 项到第 b 项qMAKE-SAME a b c
3、 n把序列的第 a 项到第 b 项的值统一改为cqREVERSE a b n把序列的第 a 项到第 b 项首尾翻转后放回原位qGET-SUM a b n输出序列的第 a 项到第 b 项的和qMAX-SUMn求序列中和最大的一段非空子列，并输出最大和如何解决好动态统计问题中山一中 余江伟【例一】维护序列【例一】维护序列 (NOI2005)n写一个程序维护一个序列qINSERT a ckqDELETE a b qMAKE-SAME a b c qREVERSE a b qGET-SUM a bqMAX-SUMn任何时刻序列长度1 N 500,000n操作总数 1 M 20,000n插入数的总数1
4、K 4,000,000 如何解决好动态统计问题中山一中 余江伟【例一】维护序列【例一】维护序列 (NOI2005)n初步分析q本题需要模拟一个序列的变化过程并随时统计相关求和信息q具有操作种类多、规模大的特点q朴素算法n数组/链表模拟，只能拿到部分分数q更优秀的算法n块状链表（参考解答），综合数组、链表的优势n树形结构树形结构如何解决好动态统计问题中山一中 余江伟【例一】维护序列【例一】维护序列 (NOI2005)n关键问题表示&操作如何解决好动态统计问题中山一中 余江伟【例一】维护序列【例一】维护序列 (NOI2005)n关键问题表示&操作q如何表示n二叉查找树(BST)表示序列n每个节点记
5、录一个数nBST中序遍历结果为原序列一棵表示(-5,-2,-1,1,6,-7,8,10,-5,19,0,21,22,3,-4)的BST8619-5-2-71-110-522-43210如何解决好动态统计问题中山一中 余江伟【例一】维护序列【例一】维护序列 (NOI2005)n关键问题表示&操作q如何操作n不难发现，大多数操作都是围绕某个“连续段”进行的n“连续段”在BST中可能比较分散，我们希望把这些节点聚集起来n伸展树如何解决好动态统计问题中山一中 余江伟【例一】伸展树简介【例一】伸展树简介n伸展树是一种自适应(Self-Adjusting)的BST。具体地说，每次访问一个节点后，按照一定规
6、则进行旋转，将其调整为树的根。如何解决好动态统计问题中山一中 余江伟【例一】伸展树简介【例一】伸展树简介n伸展树是一种自适应(Self-Adjusting)的BST。具体地说，每次访问一个节点后，按照一定规则进行旋转，将其调整为树的根。n伸展树的旋转规则qZig/ZagqZig-Zig/Zag-ZagqZig-Zag/Zag-Zig如何解决好动态统计问题中山一中 余江伟【例一】伸展树简介【例一】伸展树简介n伸展树是一种自适应(Self-Adjusting)的BST。具体地说，每次访问一个节点后，按照一定规则进行旋转，将其调整为树的根。n伸展树的旋转规则qZig/ZagqZig-Zig/Zag-
7、ZagqZig-Zag/Zag-ZigxyA AB BC CxyA AB BC C如何解决好动态统计问题中山一中 余江伟【例一】伸展树简介【例一】伸展树简介n伸展树是一种自适应(Self-Adjusting)的BST。具体地说，每次访问一个节点后，按照一定规则进行旋转，将其调整为树的根。n伸展树的旋转规则qZig/ZagqZig-Zig/Zag-ZagqZig-Zag/Zag-ZigyzA AC CD DxyA AB BC CxB BzD D如何解决好动态统计问题中山一中 余江伟【例一】伸展树简介【例一】伸展树简介n伸展树是一种自适应(Self-Adjusting)的BST。具体地说，每次访问
8、一个节点后，按照一定规则进行旋转，将其调整为树的根。 n伸展树的旋转规则qZig/ZagqZig-Zig/Zag-ZagqZig-Zag/Zag-ZigyzC CD DxzD DB BA AxB BC CyA A如何解决好动态统计问题中山一中 余江伟【例一】伸展树简介【例一】伸展树简介n按照以上规则将节点调整到根的过程称为伸展伸展操作操作。可以证明，伸展操作的平摊复杂度为O(logN)。n利用伸展操作，可以完成所有BST的基本操作。n针对本题，在节点上记录子树的大小(Size)，可以实现第K个节点的查找功能(SplayKth)。这也是解决本题的核心过程。如何解决好动态统计问题中山一中 余江伟【
9、例一】核心过程伪代码【例一】核心过程伪代码(1)SplayKth(p, kth) / 把以把以 p为根的子树下第为根的子树下第kthkth个节点提到子树的根，并返回节点编号个节点提到子树的根，并返回节点编号1 if SizeLeftp+1 = kth then return p2 if SizeLeftp kth3 then x Leftp4 if SizeLeftx+1 = kth then return Zig( x, p )5 if SizeLeftx kth then6 return Zig-Zig( SplayKth(Leftx, kth), x, p )7 kth kth - Si
10、zeLeftx 18 return Zig-Zag( SplayKth(Rightx, kth), x, p )9 else / / 目标节点在右子树的情况可类似处理目标节点在右子树的情况可类似处理如何解决好动态统计问题中山一中 余江伟【例一】操作分析【例一】操作分析插入插入n对一棵有N个节点、具有树根Root的伸展树执行一次 RootSplayKth(Root, K) 所查询节点位于树根，前K-1个节点被聚集在根的左子树上，后N-K个节点被聚集在根的右子树上。n利用这个性质，可以实现对“连续段”的插入插入如何解决好动态统计问题中山一中 余江伟8619-5-2-71-110-522-43210
11、【例一】操作分析【例一】操作分析插入插入在第在第8项后插入一个项后插入一个“连续段连续段”如何解决好动态统计问题中山一中 余江伟8619-5-2-71-110-522-432108619-5-2-71-110-522-43210找到第找到第8项：红色节点项：红色节点19【例一】操作分析【例一】操作分析插入插入如何解决好动态统计问题中山一中 余江伟8619-5-2-71-110-522-43210-14【例一】操作分析【例一】操作分析插入插入在根与右子树之间插入在根与右子树之间插入“连续段连续段”黄色三角形是一棵完美二叉树黄色三角形是一棵完美二叉树如何解决好动态统计问题中山一中 余江伟n对一棵有
12、N个节点、具有树根Root的伸展树执行一次 RootSplayKth(Root, K) 所查询节点位于树根，前K-1个节点被聚集在根的左子树上，后N-K个节点被聚集在根的右子树上。n进一步地，在Root的左子树上，再次利用这个性质，可以实现对“连续段”的提取提取【例一】操作分析【例一】操作分析提取提取如何解决好动态统计问题中山一中 余江伟8619-5-2-71-110-522-43210【例一】操作分析【例一】操作分析提取提取提取第提取第511项项如何解决好动态统计问题中山一中 余江伟8619-5-2-71-110-522-43210黄色节点为所求黄色节点为所求“连续段连续段”【例一】操作分析
13、【例一】操作分析提取提取如何解决好动态统计问题中山一中 余江伟8619-5-2-71-110-522-43210红色节点代表与红色节点代表与“连续段连续段”相邻的左右两项相邻的左右两项【例一】操作分析【例一】操作分析提取提取如何解决好动态统计问题中山一中 余江伟22-432108619-5-2-71-110-522-432108619-5-2-71-110-5【例一】操作分析【例一】操作分析提取提取将右端红色节点提到根将右端红色节点提到根如何解决好动态统计问题中山一中 余江伟22-432108619-5-2-71-110-510-5223-4086-5-2-71-11921【例一】操作分析【例
14、一】操作分析提取提取将右端红色节点提到根将右端红色节点提到根如何解决好动态统计问题中山一中 余江伟10-5223-4086-5-2-71-11921把左端红色节点提到左子树的根把左端红色节点提到左子树的根【例一】操作分析【例一】操作分析提取提取如何解决好动态统计问题中山一中 余江伟10-5223-4086-5-2-71-119216-5-2-71-110-5223-4081921【例一】操作分析【例一】操作分析提取提取把左端红色节点提到左子树的根把左端红色节点提到左子树的根如何解决好动态统计问题中山一中 余江伟6-5-2-71-110-5223-408192110-5086-2-71-119-
15、5223-421【例一】操作分析【例一】操作分析提取提取把左端红色节点提到左子树的根把左端红色节点提到左子树的根如何解决好动态统计问题中山一中 余江伟10-5086-2-71-119-5223-421成功提取第成功提取第511项！项！【例一】操作分析【例一】操作分析提取提取如何解决好动态统计问题中山一中 余江伟10-5086-2-71-119-5223-421n对“连续段”进行操作qDeleten直接删除子树qGet-Sumn维护每个节点的子树所赋值(Value)的和(Sum)即可qReverse & Make-Samen分别设置标记标记，访问节点前处理处理并向子树传递传递【例一】操作分析【例
16、一】操作分析如何解决好动态统计问题中山一中 余江伟【例一】操作分析【例一】操作分析nMax-Sumq维护信息n子树内最大子列和(AllMax)n子树左/右起最大和(LMax, RMax)q动态规划求解q直接输出根节点的AllMax值8619-5-2-71-110-522-43210如何解决好动态统计问题中山一中 余江伟n注意事项q随着节点附加信息增多，需要适当修改核心过程SplayKthq提取“连续段”a, b时，用到以下代码： Root SplayKth(Root, b+1) LeftRoot SplayKth(LeftRoot, a-1)为避免边界情况(b=SizeRoot或a=1)的讨论
17、，在首尾增加两个空白节点，并把输入数据的位置x替换为x=x+1【例一】细节处理【例一】细节处理如何解决好动态统计问题中山一中 余江伟SplayKth(p, kth) / 把以把以 p为根的子树下第为根的子树下第kthkth个节点提到子树的根个节点提到子树的根1 处理处理 Leftp 和和 Rightp 的标记的标记2 if SizeLeftp+1 = kth then return p3 if SizeLeftp kth4 then x Leftp5 处理处理 Leftx 和和 Rightx 的标记的标记6 if SizeLeftx+1 = kth then return Zig( x, p
18、)7 if SizeLeftx kth then8 return Zig-Zig( SplayKth(Leftx, kth), x, p )9 kth kth - SizeLeftx 110 return Zig-Zag( SplayKth(Rightx, kth), x, p )11 else / / 目标节点在右子树的情况可类似处理目标节点在右子树的情况可类似处理【例一】核心过程伪代码【例一】核心过程伪代码(2)改变树的形态改变树的形态后维护最大和后维护最大和如何解决好动态统计问题中山一中 余江伟【例一】性能比较【例一】性能比较如何解决好动态统计问题中山一中 余江伟n面对大规模的统计问题，
19、对边界范围离散化离散化，是减小问题规模的有效手段。n习惯上，离散化的过程在主算法之前执行。这是统计对象之间次序的固定所带来的便利。n如果统计对象次序发生变化，该如何应对？如何解决好动态统计问题中山一中 余江伟【例二】文本编辑器【例二】文本编辑器 (NOI2003)n模拟一个字符串的变化过程。可能的操作有：qINSERT: 在光标处插入字符串qDELETE: 删除光标后n个字符qGET: 输出光标后n个字符，正确的输出总字符数不超过3MqMOVE: 将光标移动到当前第k个字符之后qPREV / NEXT: 光标向前/后移动一位n数据范围q插入的总字符数不超过221q插入(Insert)和删除(D
20、elete)的总次数不超过4000如何解决好动态统计问题中山一中 余江伟【例二】文本编辑器【例二】文本编辑器(NOI2003)n模型分析把光标移动的操作累积起来，需要时再定位，问题转化为【例一】的简化版：nINSERTnDELETEnGET虽然我们可以沿用【例一】提到的解法，但本题有更简单的算法。突破口就在于增删操作次数上限与插入字符总数上限之间的巨大落差！总共不超总共不超过过4000次次4000 221 如何解决好动态统计问题中山一中 余江伟【例二】文本编辑器【例二】文本编辑器(NOI2003)n感性认识q两个数值之间的差距意味着：在执行少量增删指令后，字符串的长度可能已经达到一个较大的数目
21、，但字符间的次序关系并未被大规模打乱。 n理性分析q如果把每次插入的字符串看作一个具有连续属性的区间，那么我们所说的“打乱”就是指某次增删操作对区间的划分和排列。随着增删操作的进行，区间的划分也越来越细。这一过程即为离散化离散化。如何解决好动态统计问题中山一中 余江伟【例二】文本编辑器【例二】文本编辑器(NOI2003)n举例说明 操作INSERT 0 “Balanced_tree”区间划分与排列情况 & 输出字符串124567810 1112 13 15 16 17 18 19 203149如何解决好动态统计问题中山一中 余江伟【例二】文本编辑器【例二】文本编辑器(NOI2003)n举例说明
22、BaancedTree l_操作INSERT 0 “Balanced_tree”区间划分与排列情况 & 输出字符串1, 13124567810 1112 13 15 16 17 18 19 203149如何解决好动态统计问题中山一中 余江伟【例二】文本编辑器【例二】文本编辑器(NOI2003)n举例说明BaancedTree l_操作INSERT 0 “Balanced_tree”DELETE 3 7区间划分与排列情况 & 输出字符串1, 131, 2 8, 13124567810 1112 13 15 16 17 18 19 203149如何解决好动态统计问题中山一中 余江伟【例二】文本编辑
23、器【例二】文本编辑器(NOI2003)n举例说明BaancedTree l_操作INSERT 0 “Balanced_tree”DELETE 3 7INSERT 3 “_editor”区间划分与排列情况 & 输出字符串1, 131, 2 8, 13124567810 1112 13 15 16 17 18 19 203149如何解决好动态统计问题中山一中 余江伟n举例说明BaancedTree l_操作INSERT 0 “Balanced_tree”DELETE 3 7INSERT 3 “_editor”区间划分与排列情况 & 输出字符串1, 131, 2 8, 131, 2 8, 8 9,
24、13BaancedTree editorl_124567810 1112 13 15 16 17 18 19 20314914, 20【例二】文本编辑器【例二】文本编辑器(NOI2003)1243如何解决好动态统计问题中山一中 余江伟【例二】文本编辑器【例二】文本编辑器(NOI2003)n举例说明操作INSERT 0 “Balanced_tree”DELETE 3 7INSERT 3 “_editor”GET 1, 16区间划分与排列情况 & 输出字符串1, 131, 2 8, 131, 2 8, 8 14, 20 9, 13“Bad_editor_Tree”124567810 1112 13
25、 15 16 17 18 19 203149BaancedTree l_BaancedTree editorl_1243如何解决好动态统计问题中山一中 余江伟【例二】文本编辑器【例二】文本编辑器(NOI2003)n算法分析q把读入的字符串按顺序存储在大数组里。q在整个过程中，变化的只是各区间的端点与排列顺序，无需对字符串作任何改动。q每次增删操作新划分出的区间数不超过2个，而增删操作总数不超过4000，所以总区间数不超过8000。问题规模大大降低问题规模大大降低字符串操作字符串操作区间操作区间操作离散化思想离散化思想如何解决好动态统计问题中山一中 余江伟【例二】文本编辑器【例二】文本编辑器(N
26、OI2003)n算法的优化q区间划分越来越细区间总数越来越多q当区间总数达到一定数量(Limit)后，按顺序将多个区间合并成一个1, 2 8, 8 14, 20 9, 131, 15BaancedTree editorl_Bad_editro_Tree124567810 1112 13 15 16 17 18 19 203149如何解决好动态统计问题中山一中 余江伟【例二】文本编辑器【例二】文本编辑器(NOI2003)n算法的优化q一次整理的复杂度高达O(C) （C为字符串长度）整理少了区间数量太多整理多了反而成为瓶颈q利用几何平均思想，平衡两者的矛盾q理论上，在满足以下等式情况下复杂度最低：q实际中，把区间上限设置为1000左右较好如何解决好动态统计问题中山一中 余江伟【总结】【总结】n纵观整个过程，要解决好动态统计问题，需要灵活运用数据结构灵活运用数据结构，并融入各种深刻的算法思融入各种深刻的算法思想想，从而高效地解决问题n面对纷繁复杂的问题，要经过冷静的分析，抓住共同点共同点，写出紧凑的代码n遇到简化版的问题，不要轻易跳过，尝试一题一题多解，拓宽思路多解，拓宽思路纸上得来终觉浅，绝知此事要躬行纸上得来终觉浅，绝知此事要躬行如何解决好动态统计问题中山一中 余江伟如何解决好动态统计问题中山一中 余江伟
