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

作     者：冯志勇 石逸可 石俊萍 FENG Zhi-yong;SHI Yi-ke;SHI Jun-ping

作者机构：吉首大学计算机科学与工程学院湖南吉首416000 

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

出 版 物：《电脑与信息技术》 (Computer and Information Technology)

年 卷 期：2023年第31卷第4期

页      码：46-48页

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

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

学科分类：08[工学] 081202[081202] 0812[工学-测绘类] 

D　O　I：10.19414/j.cnki.1005-1228.2023.04.019

馆 藏 号：203122711...