浅谈分块思想 在一类数据处理问题中的应用,北京市第八十中学 罗剑桥,本文讨论的范围,一类与线性序列和树形结构有关的数据处理问题 特征： 1. 在竞赛中常常出现 2. 没有专门的数据结构解法 或者数据结构解法十分复杂,什么是分块思想,将一个问题分解为若干个规模较小的子问题 优势： 1. 如果子问题的规模很小，可以设计关于子问题规模的 复杂度较高的算法； 2. 如果子问题的数目很少，可以对每类子问题使用复杂 度与整个问题规模有关的算法； 3. 如果每个子问题内部的元素具有共同的性质，可以使 用针对性的算法。,线性序列的分块化,从第一个元素开始，每连续的 S 个元素组成一个块。若剩余的元素不足 S 个，令它们组成一个块。 例子：序列元素数目 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 = 105. 任意时刻所有数均为绝对值不超过109的整数。,例一：样例,N = 5, M = 4. 7 15 11 8 2 ADD: Di = 2, Xi = 1 8 15 12 8 3 ASK: Li = 1, Ri = 4 answer: 8 + 15 + 12 + 8 = 43 ADD: Di = 4, Xi = -5 3 15 12 8 3 ASK: Li = 1, Ri = 4 answer: 3 + 15 + 12 + 8 = 38,例一：分析,将序列分块，令每块的大小为 。 考虑在块的层次上维护每个块的所有元素的和。 首先，预处理的复杂度为 O(N) 。 1.对于询问操作，只需计算出询问区间对应的完整的块与多余的元素的和，时间复杂度为 O( )。 N = 10. Ask: Li = 3, Ri = 8. 3, 4, 5 1, 2, 3 7, 8, 9 10 answer = 5 + 6 + 7 + 8 = 26. 2.对于修改操作，复杂度还是很高，怎么办呢?,例一：分析,这时还是要用到分块的思想。 发现，只有当 Di 比较小的时候修改的元素才会很多。 解决方法： 1. 每个元素和块只考虑 Di = 的修改操作的影响。 2. 用数组记录 Di 的每个 Di 的修改量的和。 在查询时枚举每个小于 的 Di，O(1) 计算对答案的影响即可。 此算法总的时间复杂度为O(n + m )。,例一：分析,N = 10 3, 4, 5 1, 2, 3 7, 8, 9 10 1.ADD Di = 1, Xi = 3 Sum: 12, 6, 24, 10; Di13: 3, 0, 0. 2.ADD Di = 4, Xi = 1. 4, 4, 5 1, 3, 3 7, 8, 10 10 Sum: 13, 7, 25, 10; Di13: 3, 0, 0.,树形结构的分块化,树的 DFS 序： 从根开始深度优先遍历，每次遇到一个点进栈或出栈，就把它放到 DFS 序列的末尾。,1 1, 2 1, 2, 4 1, 2, 4, 4 1, 2, 4, 4, 5 1, 2, 4, 4, 5, 5 1, 2, 4, 4, 5, 5, 2 1, 2, 4, 4, 5, 5, 2, 3 1, 2, 4, 4, 5, 5, 2, 3, 3 1, 2, 4, 4, 5, 5, 2, 3, 3, 1,DFS序的性质,1. 相邻两个元素之间仅有三种关系： 同一个点；父子关系；兄弟关系。 2. 任意两项之间的连续子序列恰好对应了树上 一条路径，路径上除 LCA 以外的点至少出现1次。 3. DFS 序列中任意一个区间以及这个区间所有元素 的 LCA 恰好对应树上的一个连通块。 将 DFS 序列分块，每一块与其 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, 10 distance2: 3, 5, 7, 13 distance3: 10, 13, 18, 20 distance4: 5, 8, 12, 18 distance5: 7, 10, 12, 20,例二：分析,相邻的点之间的答案具有很强的相关性： 设点 u 的答案为 ansu. 若存在一条边 (u, v) 的权值等于 c, 则点 v 的答案是 ansu - c 到 ansu + c 之间的数。 考虑将树分成若干个规模等于 S 的连通块。 一次计算出一个连通块内所有点的答案。,例二：分析,对一个连通块，以块内的某个点为根。 性质 1： 无论以块内的哪个点为根，每个点到根的路径上的第一个块内的点是不变的。 推论： 将所有点按最近块内祖先分类。 考虑同类的点 u, v，设 p 为 u 和 v 的最近块内祖先。 则 点 u 到根的距离 点 u 到 p 的距离 = 点 v 到 p 的距离,例二：分析,例二：分析,1. 对于一个连通块，首先以一个点 r 遍历全树，计算出每类点到最近块内祖先 (LIA) 的距离。 并且将每类点按到 LIA 的距离排序。 2. 然后，依次计算块内每个点的答案。 使用二分答案的办法。 3. 如何统计到点 ri 距离不超过 x 的点的数目？ 以 ri 为根遍历块内的所有点，算出它们到 ri 的距离。 对每类点二分查找 加上 LIA 到 ri 的距离以后不 超过 x 的最大的数的位置即可。,例二：复杂度分析,连通块的大小为 S。 第一次遍历和排序的时间复杂度为 O(NlogN). 每个点，二分答案和查找的时间复杂度为 O(log2N). 所以处理一个块的复杂度是 O(NlogN + Slog2N). 总的时间复杂度为 O(N2logN/S + NSlog2N). 如果设 S = ， 总的时间复杂度为 O(N1.5log1.5N) .,分块与预处理,预处理的条件 线性序列上，预处理任意两块之间的信息，每次询问时经过若干次增量得到询问区间的信息。 树形结构中，贪心算法标记若干关键点，预处理任意两个关键点之间的信息，每次询问时经过若干次增量得到询问路径的信息。,分块与离线算法,与分块与预处理的方法有一定的相似之处。 核心： 没有必要记录过多信息， 在预处理的同时计算询问的答案。 具体可参考论文。,感谢,感谢中国计算机学会。 感谢我的指导老师贾志勇老师长期以来的关心和帮助。 感谢集训队的胡伟栋教练和唐文斌教练。 特别感谢北京人大附中的范浩强同学的大力帮助和启发。 感谢学长黄纪元同学的帮助。 感谢我的父母对我的无微不至的关心和照顾。,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”命题报告. 徐捷, “图中图”命题报告. 许昊然, 数据结构漫谈.,