第31卷第4期2023年8月Vol.31No.4Aug.2023电脑与信息技术ComputerandInformationTechnology文章编号：1005-1228（2023）04-0046-03程序设计竞赛ACM中树链剖分的研究冯志勇，石逸可，石俊萍（吉首大学计算机科学与工程学院，湖南吉首416000）摘要：线段树在ACM大学生程序竞赛中应用非常广泛，是解决区间问题的一把利器，但对于树形数据结构线段树不能适用，考虑采用树链剖分进行操作。先从线段树的定义出发，讲述线段树的存储方式、建树、区间操作等原理及其实现，分析了线段树各个操作的时间复杂度并与其他算法进行对比。随后引出树链剖分使用重轻链分离的方法对线段树进行改进使之可以解决树上的操作问题；并以例题的方式介绍了树链剖分的应用。关键词：ACM；程序设计；线段树；树链剖分；重链；长链；DFS；中图分类号：TP301.6文献标识码：AResearchonTreeChainDivisioninProgrammingCompetitionACMFENGZhi-yong,SHIYi-ke,SHIJun-ping（SchoolofComputerScienceandEngineering,JishouUniversity,Jishou416000,China）Abstract：SegmenttreeiswidelyusedinACMprogramcompetition.Itisapowerfultooltosolveintervalproblems.However,segmenttreeisnotsuitablefortreedatastructure.Startingfromthedefinitionoflinesegmenttree,thispaperdescribesthestoragemode,treeconstruction,intervaloperationandotherprinciplesoflinesegmenttree,andanalyzesthetimecomplexityofeachoperationoflinesegmenttreeandcompareswithotheralgorithms.Then,thetreechaindivisionisintroduced.Themethodofheavyandlightchainseparationisusedtoimprovethelinesegmenttreesothatitcansolvetheoperationproblemofthetree.Anexampleisgiventointroducetheapplicationoftreechainsubdivision.Keywords:ACM;programdesign;linesegmenttree;treechainsubdivision;heavychain;longchain;DFS;收稿日期：2022-11-23基金项目：湖南省2022年大学生创新创业训练项目《智慧图书馆系统的设计与开发》（项目序号3532）。作者简介：冯志勇（2002-），男，本科在读，主要研究方向为计算机软件技术；石俊萍（1974-），女，湖南花垣人，副教授，硕士，主要研究方向为计算机软件技术；（通信作者）石逸可（2002-），男，本科在读，主要研究方向为计算机软件技术。大学生程序设计竞赛[1][4][5]是大学生比赛中含金量非常之高的存在，其中ICPC（国际大学生程序设计竞赛）更是誉为大学生程序...
