程序设计竞赛中线段树的四类典型应用场景

扫码查看

原文链接

万方数据
维普

中文摘要：线段树是程序设计竞赛的重要知识点,应用场景复杂多变且不单独作为模板考察.现有教材和文献仅对线段树的基本理论与模板实现做了解析,而未对其在竞赛中的应用场景进行归类总结.学生只能依靠大量的习题训练和竞赛经验积累,才能摸清门路.对此,本文归纳出了关于线段树在程序设计竞赛中的四类典型应用场景:"扫描线算法的优化"、"树形结构信息的维护"、"带修改的结合律信息的维护"和"动态规划算法的优化",并针对每类场景进行举例与解析.以期帮助学生对线段树的应用建立系统性的认识,从而降低学习难度,缩短学习周期,提升学习效率.

外文标题：Four typical application scenarios of segment trees in programming contests

作者：

符智基、赵义霞、刘利

展开 >

作者单位：

惠州学院计算机科学与工程学院,广东惠州 516007

关键词：

程序设计线段树扫描线算法树形结构动态规划的优化结合律

基金：

广东省高等教育教学改革项目

项目编号：

2019-570

出版年：

2023

DOI：

10.16644/j.cnki.cn33-1094/tp.2023.01.027

计算机时代

浙江省计算技术研究所　浙江省计算机学会

计算机时代

影响因子：0.411

ISSN：1006-8228

年,卷(期)：2023.(1)

参考文献量6