1、浅谈分块思想在一类数据处理问题中的应用,北京市第八十中学罗剑桥,本文讨论的范围,一类与线性序列和树形结构有关的数据处理问题特征：1. 在竞赛中常常出现2. 没有专门的数据结构解法 或者数据结构解法十分复杂,什么是分块思想,将一个问题分解为若干个规模较小的子问题优势：1. 如果子问题的规模很小，可以设计关于子问题规模的 复杂度较高的算法；2. 如果子问题的数目很少，可以对每类子问题使用复杂 度与整个问题规模有关的算法；3. 如果每个子问题内部的元素具有共同的性质，可以使 用针对性的算法。,线性序列的分块化,从第一个元素开始，每连续的 S 个元素组成一个块。若剩余的元素不足 S 个，令它们组成一个
2、块。例子：序列元素数目 N = 7，块的大小S = 3.,线性序列的分块化：性质,设 N 为序列的元素数目，S 为块的大小。1. 块的数目不超过 N / S + 1. 2. 对于任意区间 L, R, 可以分解成若干个完整的 块以及剩余的不超过 2S 个元素。如果能在块的层次上概括块内元素的信息，并且可以快速将不同部分的信息合并，就能够快速地得到任意区间的信息了。,例一,一个 N 个数的序列。你要执行 M 次操作。操作有两种类型：1. 从第一个数开始，每隔 Di 个位置的数加上 Xi。2. 查询区间 Li, Ri 的所有元素的和。1 = N, M = 的修改操作的影响。2. 用数组记录 Di 的
3、每个 Di 的修改量的和。 在查询时枚举每个小于 的 Di，O(1) 计算对答案的影响即可。此算法总的时间复杂度为O(n + m )。,例一：分析,N = 103, 4, 5 1, 2, 3 7, 8, 9 101.ADD Di = 1, Xi = 3Sum: 12, 6, 24, 10; Di13: 3, 0, 0.2.ADD Di = 4, Xi = 1. 4, 4, 5 1, 3, 3 7, 8, 10 10Sum: 13, 7, 25, 10; Di13: 3, 0, 0.,树形结构的分块化,树的 DFS 序： 从根开始深度优先遍历，每次遇到一个点进栈或出栈，就把它放到 DFS 序列的
4、末尾。,11, 21, 2, 41, 2, 4, 41, 2, 4, 4, 51, 2, 4, 4, 5, 51, 2, 4, 4, 5, 5, 21, 2, 4, 4, 5, 5, 2, 31, 2, 4, 4, 5, 5, 2, 3, 31, 2, 4, 4, 5, 5, 2, 3, 3, 1,DFS序的性质,1. 相邻两个元素之间仅有三种关系： 同一个点；父子关系；兄弟关系。2. 任意两项之间的连续子序列恰好对应了树上 一条路径，路径上除 LCA 以外的点至少出现1次。3. DFS 序列中任意一个区间以及这个区间所有元素 的 LCA 恰好对应树上的一个连通块。将 DFS 序列分块，每一块
5、与其 LCA 就对应了树上的一个连通块！,例二,一个 N 个点的树。边有权值。你需要计算对于每个点，其他所有点到它的距离中第 K 小的值。1 = K N = 50,000. 边的权值为绝对值不超过1,000的整数。,例二：样例,1,2,3,4,5,10,3,7,5,N = 5, K = 2.,distance1: 3, 8, 10, 10distance2: 3, 5, 7, 13distance3: 10, 13, 18, 20distance4: 5, 8, 12, 18distance5: 7, 10, 12, 20,例二：分析,相邻的点之间的答案具有很强的相关性：设点 u 的答案为 a
6、nsu.若存在一条边 (u, v) 的权值等于 c,则点 v 的答案是 ansu - c 到 ansu + c 之间的数。考虑将树分成若干个规模等于 S 的连通块。一次计算出一个连通块内所有点的答案。,例二：分析,对一个连通块，以块内的某个点为根。性质 1：无论以块内的哪个点为根，每个点到根的路径上的第一个块内的点是不变的。推论：将所有点按最近块内祖先分类。考虑同类的点 u, v，设 p 为 u 和 v 的最近块内祖先。则 点 u 到根的距离 点 u 到 p 的距离 = 点 v 到 p 的距离,例二：分析,例二：分析,1. 对于一个连通块，首先以一个点 r 遍历全树，计算出每类点到最近块内祖先
7、 (LIA) 的距离。并且将每类点按到 LIA 的距离排序。2. 然后，依次计算块内每个点的答案。 使用二分答案的办法。3. 如何统计到点 ri 距离不超过 x 的点的数目？ 以 ri 为根遍历块内的所有点，算出它们到 ri 的距离。 对每类点二分查找 加上 LIA 到 ri 的距离以后不 超过 x 的最大的数的位置即可。,例二：复杂度分析,连通块的大小为 S。第一次遍历和排序的时间复杂度为 O(NlogN).每个点，二分答案和查找的时间复杂度为 O(log2N).所以处理一个块的复杂度是 O(NlogN + Slog2N).总的时间复杂度为 O(N2logN/S + NSlog2N).如果设
8、 S = ，总的时间复杂度为 O(N1.5log1.5N) .,分块与预处理,预处理的条件线性序列上，预处理任意两块之间的信息，每次询问时经过若干次增量得到询问区间的信息。树形结构中，贪心算法标记若干关键点，预处理任意两个关键点之间的信息，每次询问时经过若干次增量得到询问路径的信息。,分块与离线算法,与分块与预处理的方法有一定的相似之处。核心：没有必要记录过多信息，在预处理的同时计算询问的答案。具体可参考论文。,感谢,感谢中国计算机学会。感谢我的指导老师贾志勇老师长期以来的关心和帮助。感谢集训队的胡伟栋教练和唐文斌教练。特别感谢北京人大附中的范浩强同学的大力帮助和启发。感谢学长黄纪元同学的帮助
9、。感谢我的父母对我的无微不至的关心和照顾。,Thank you.,Questions are welcome,参考文献,Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. “Introduction to Algorithms (2nd ed.)”, 潘金贵等译，机械工业出版社.Jon Kleinberg, Eva Tardos. “Algorithm Design”, 清华大学出版社.吴文虎, 王建德.世界大学生程序设计竞赛(ACM/ICPC)高级教程(第一册), 中国铁道出版社.郑暾, 平衡规划 浅析一类平衡思想的应用.漆子超, 分治算法在树的路径问题中的应用.莫涛, “小Z的袜子”命题报告.顾昱洲, “JZPLCM”命题报告.徐捷, “图中图”命题报告.许昊然, 数据结构漫谈.,
