程序设计竞赛ACM中树链剖分的研究  

Research on Tree Chain Division in Programming Competition ACM

作　　者：冯志勇 石逸可 石俊萍[1] FENG Zhi-yong;SHI Yi-ke;SHI Jun-ping(School of Computer Science and Engineering,Jishou University,Jishou 416000,China)

机构地区：[1]吉首大学计算机科学与工程学院,湖南吉首416000

出　　处：《电脑与信息技术》2023年第4期46-48,共3页Computer and Information Technology

基　　金：湖南省2022年大学生创新创业训练项目《智慧图书馆系统的设计与开发》(项目序号3532)。

摘　　要：线段树在ACM大学生程序竞赛中应用非常广泛,是解决区间问题的一把利器,但对于树形数据结构线段树不能适用,考虑采用树链剖分进行操作。先从线段树的定义出发,讲述线段树的存储方式、建树、区间操作等原理及其实现,分析了线段树各个操作的时间复杂度并与其他算法进行对比。随后引出树链剖分使用重轻链分离的方法对线段树进行改进使之可以解决树上的操作问题;并以例题的方式介绍了树链剖分的应用。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.

关 键 词：ACM 程序设计 线段树 树链剖分 重链 长链 DFS 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]