程序设计竞赛ACM中树链剖分的研究_冯志勇.pdf

第 31 卷 第 4 期 2023 年 8 月Vol.31 No.4Aug.2023电脑与信息技术Computer and Information Technology文章编号：1005-1228（2023）04-0046-03程序设计竞赛ACM 中树链剖分的研究冯志勇，石逸可，石俊萍（吉首大学计算机科学与工程学院，湖南 吉首416000）摘要：线段树在 ACM 大学生程序竞赛中应用非常广泛，是解决区间问题的一把利器，但对于树形数据结构线段树不能适用，考虑采用树链剖分进行操作。先从线段树的定义出发，讲述线段树的存储方式、建树、区间操作等原理及其实现，分析了线段树各个操作的时间复杂度并与其他算法进行对比。随后引出树链剖分使用重轻链分离的方法对线段树进行改进使之可以解决树上的操作问题；并以例题的方式介绍了树链剖分的应用。关键词：ACM；程序设计；线段树；树链剖分；重链；长链；DFS；中图分类号：TP301.6文献标识码：AResearch on Tree Chain Division in Programming Competition ACMFENG Zhi-yong,SHI Yi-ke,SHI Jun-ping（School of Computer Science and Engineering,Jishou University,Jishou 416000,China）Abstract：Segment tree is widely used in ACM program competition.It is a powerful tool to solve interval problems.However,segment tree is not suitable for tree data structure.Starting from the definition of line segment tree,this paper describes the storage mode,tree construction,interval operation and other principles of line segment tree,and analyzes the time complexity of each operation of line segment tree and compares with other algorithms.Then,the tree chain division is introduced.The method of heavy and light chain separation is used to improve the line segment tree so that it can solve the operation problem of the tree.An example is given to introduce the application of tree chain subdivision.Key words:ACM;program design;line segment tree;tree chain subdivision;heavy chain;long chain;DFS;收稿日期：2022-11-23基金项目：湖南省 2022 年大学生创新创业训练项目智慧图书馆系统的设计与开发（项目序号 3532）。作者简介：冯志勇（2002-），男，本科在读，主要研究方向为计算机软件技术；石俊萍（1974-），女，湖南花垣人，副教授，硕士，主要研究方向为计算机软件技术；（通信作者）石逸可（2002-），男，本科在读，主要研究方向为计算机软件技术。大学生程序设计竞赛145是大学生比赛中含金量非常之高的存在，其中 ICPC（国际大学生程序设计竞赛）更是誉为大学生程序设计竞赛中的奥林匹克，程序设计竞赛2中所考察的重点数据结构与算法更是研究的重点。线段树35是一种采用了分治思想的二叉搜索树，具有非常广的应用场景，运用在数据库系统和文件系统，进行高效率的排序和检索的操作，对于区间操作具有非常高效的效果。但是线段树更多是运用在一段连续的区间中，对于树形数据结构的数据难以进行操作。于是就有了树链剖分的研究，可以很好的解决树上的操作问题，使得线段树具有更好的适应性，并不再局限于线性数据结构，可以使用树链剖分来解决程序设计竞赛中关于树的操作问题。1线段树的研究1.1定义线段树是一种二叉搜索树，采用了分治的思想36，将每个区间长度不为 1 的区间划分为左右两个区间进行递归求解，使初始区间为线段树的初节点，将区间折半划分成为线段树的左右节点，单位区间为线段树的叶子节点，叶子节点个数则是区间长度。1.2原理线段树的结点储存的值是一个区间内的某个所需要的值，采用递归储存的方式将区间数据折半划DOI:10.19414/ki.1005-1228.2023.04.019第 31 卷 第 4 期47冯志勇等，程序设计竞赛 ACM 中树链剖分的研究分并储存，对于 L,R 这样一个区间，初始节点储存这个初始区间，左节点储存 L,(L+R)/2，右节点储存(L+R)/2+1,R，依次往底部递推直到区间长度为 1，所以线段树可以用来解决查询区间最大值和最小值还能进行查询特定区间的和这类区间问题，时间复杂度相较于直接搜索具有很高的效率，达到了 O(log2 n)。1.3线段树的函数功能线段树首先需要建树，将线段树的所有节点初始化为需要被维护的数组相应区间的初值。线段树修改分为两种，一种是稍为简单的单点修改，还有一种是区间修改，当单点修改时是不需要懒惰标记的，直接通过遍历到叶子节点修改即可，而区间修改需要懒惰标记来标记哪些区间需要修改，并用懒惰标记来存储需要修改的值。当遍历到的区间包含在所需修改的区间内时，只需改变该区间的值，并加上其懒惰标记的值。因此线段树可以维护具有结合性运算的值，例如最大值和最小值，区间和。如若修改，只需将区间最值加上相应的懒惰标记即可，这样对最后的查询才不造成影响。下文查询以查询区间和为例。2树链剖分的原理及其实现2.1定义树链剖分实际上就是将一棵树划分为一条一条的链使之可以维护树上路径的信息，简单来说就是将整棵树划分成了若干条链并将其组合成了线性结构，这样就可以使用数据结构去维护，一般划分标准有两种一种是重轻链还有一种长链划分，而所用数据结构一般为上文所提到的线段树。重链剖分使得树上的每个节点都属于且仅仅属于一条重链，这样所有的重链将整棵树完全剖分，并且重链内的 DFS 序是连续的，这样就保证了树上路径是连续的便于数据结构去维护。2.2原理我们给出一些关于树链剖分的定义；定义重子节点表示为子节点中子树数量最大的子节点，如果有多个重子节点，取其中一个即可，如果没有子节点，那么就没有重子节点。定义轻子节点表示剩余的所有子节点。那么从某个节点到重子节点的边就称为中变，到其他轻子节点的边为轻边，若干个首尾相连接的重边就构成了重链，并且将落单的节点也当成重链，这样一棵树就不重不漏的被剖分成了若干条链如图 1 所示：图 1重链剖分结果2.3具体实现一棵子树的 DFS 序是连续的，并且当向下经过一条轻边时，所在的子树的大小至少是二，所以对于树上的任意一条路径，拆成从最近公共祖先分别往下方走，最多只会走 log2 n 次，因此复杂度就被大大降低为 O(log2 n)。对于树的存储采用链式前向星的方式存储，并用C+stl 库中的 vector 来缩小内存避免内存浪费。对于重链剖分需要两遍 DFS，第一遍预处理出每个节点的深度（DEP），子树大小（SIZ)，重子节点(SON)，父节点(FA)，第二遍预处理则是记录每条链的顶端节点（TOP），重边优先遍历时的DFS序（DFN），DFS 序所代表的节点编号（RNK）。当所有预处理完成后便可以进行跳链使得树上两点路径的 DFS 序是连续的这样就可以依靠数据结构去处理。2.3.1 第一次预处理C+代码如图 2 所示：图 2第一次预处理的代码2.3.2 第二次预处理C+代码图 3 所示：图 3第二次预处理的代码电脑与信息技术 2023 年 8 月482.3.3 修改树上某两个点之间的区间和C+代码如图 4 所示：图 4修改树上两点的代码2.3.4 树上两点的路径和C+代码如图 5 所示：图 5统计树上两点路径和代码3实际应用3.1题目描述以洛谷 P3384 这题为例已知一颗包含 N 个节点的树（连通且无环），每个节点上包含一个数值，需要支持以下操作（1）x y z，表示将树从 x 到 y 节点最短路径上所有节点的值都加上 z（2）x y，表示求树从 x 到 y 节点最短路径上所有节点的值之和（3）x z，表示将 x 为跟节点的子树内所有节点值都加上 z（4）x，表示求以 x 为根节点的子树内所有节点值之和进行 M 次操作1N=10000,1M=100000,1z=1000003.2问题分析首先这是个树上问题并且需要对于树上的值进行一个维护，我们首先考虑线段树，但是线段树只能对线性的数据进行维护，于是就用树链剖分来对树进行划分使其可以使用线段树维护，其复杂度是O(log2 n)，于是总共的复杂度就是 O(nlog2 n),但分析其数据范围可知最后的答案已经超过了 int 所能表示的范围，所以最后答案使用 long long int 来存储。朴素算法需要通过 DFS 进行搜索再进行维护这样的复杂度非常的大，对比朴素算法树链剖分可以很快的解决此题。4结束语程序设计竞赛不断发展，所需要的算法也越来越多，特别是如今的程序设计竞赛特别注重树上问题的解决，于是树链剖分这类的算法的研究则是必不可少的，对于 ACM 来说理解代码是必不可少的，但在理解代码之后也要试着进行一些变式加深理解并且多去思考和练习。参考文献：1 王睿,李华,张宇昕，等.基于大学生程序设计竞赛平台建设的程序设计类课程教学实践与研究 J.电脑知识与技术,2021,17(01):190-192.2 张乐,毛玉萃,侯瑞辰.程序设计竞赛中线段树问题的研究 J.电脑知识与技术,2021,17(25):160-164.3 闵慧,李鹏,邹伟红,等.一种基于线段树维护的区间方差求解算法 J.信息技术,2022(04):71-78+84.4（日）渡部有隆著.挑战程序设计竞赛 2 算法和数据结构M.北京：人民邮电出版社,2016.09.5 刘汝佳.算法竞赛入门经典(第 2 版)M.北京：清华大学出版社,2014.6 THOMAS H.CORMEN CHARLES E.LEISERSON RONALD L.RIVEST CLIFFORD STEIN 著.算法导论(第 2 版)M.北京：机械工业出版社,2006.