程序设计竞赛中线段树问题的研究

张乐 毛玉萃 侯瑞辰

摘要：介绍了程序设计竞赛中线段树的重要性;概括了线段树的作用、原理，较详细地介绍了相关的函数——建树、修改和查找;以例题方式介绍了线段树的应用;最后进行了总结。

关键词：程序设计;线段树;实例

中图分类号：TP311.52      文献标识码：A

文章编号：1009-3044（2021）25-0160-05

1 背景

大学生程序设计竞赛作为业内认可的比赛鼓励了一批又一批的大学生投入到程序设计之中。数据结构和算法作为比赛考察的重点是很值得研究的。

1.1为什么要参加程序设计竞赛

程序设计竞赛可以提高一个软件工程师的综合水平，提升基本的代码能力以及其对细节的把握能力，能增强人的团队合作、思维水平和毅力[1-2]。

1.2为什么需要研究线段树问题

线段树是一种树形数据结构，是一种二叉搜索树。二叉搜索树一般用于数据库系统和文件系统，被用于进行高效率的排序与检索操作。而线段树不仅有较高效率的排序和检索操作的功能，还可以高效的计算某段区间和修改功能[1-3]。

研究线段树问题可以用来解决程序设计竞赛中的一些相关问题，总结线段树的使用方法及范围。熟悉常见的线段树处理问题及其解法，尽多掌握程序设计类竞赛中的典型线段树问题，以利于在比赛中取得成绩[1-3]。

1.3研究线段树问题的意义

线段树问题在最近几年的大学生程序设计竞赛中的频繁出现以及之前的比赛中因对于线段树问题研究的不透彻而与奖牌失之交臂，引起了同学们对线段树问题的重视[1-3]。

2线段树的理论分析

2.1 线段树的作用

当需要维护一个数组时，需要多次查询区间有结合性的运算区间的运算结果（如区间最值，加和，乘积，异或等）并进行有结合性的修改操作（区间加，区间乘，区间异或）时，若数组的长度达到10000以上的量级，查询修改也达到10000以上的量级时，n表示数组大小，m表示操作次数，朴素的时间复杂度为[O（nm）]，直接进行修改和查询在数据极端时（如查询和修改10000次区间[1，10000]），循环遍历次数已经达到了亿级，对于1s的限时已经很难通过。而一般需要线段树的题目数据范围大都是100000的级别，并且会包括极端的样例卡掉朴素方法，所以就需要复杂度更低的算法。分块算法虽然也可以通过100000级，但在数字更大时，分块算法的[O（msqrtn）]在常数稍大时就已无法通过。因此就需要复杂度在[O（mlogn）]及以下的方法[1，4]。

线段树可以在[Ologn]复杂度内完成单次区间修改和查询操作，这样总的时间复杂度就是[O（logn）]了。

2.2 线段树的原理

线段树是一种二叉搜索树，每个节点代表一个区间，其中根节点代表要维护的整个数组区间，其它节点都代表父节点的区间的一半，从而保证深度为，每个节点储存了区间的和（该区间的和为需要维护的结合性操作），当回答询问时回答代表相应所有区间的和。当修改时以懒标记记录当前节点的所有子节点也需要进行修改，但是如果不访问它的子节点，就不需要将修改落实到子节点，所以称为懒标记。如此也保证了修改时的时间复杂度也不会超过[O（logn）][1，4]。

2.3 线段树的函数功能

线段树至少需要建树函数，其功能是初始化线段树，将线段树的所有节点置为要维护的数组相应区间的初值。

如需修改，分为单点修改和区间修改，当只需要单点修改时无须懒标记，只需遍历到相应的叶子节点并修改其值即可;而当需要区间修改时，当前遍历到的节点被包含在要修改的区间中的时候，只需修改该节点的值并相应修改其懒标记。如修改为区间加，查询为区间最小值时将该节点代表的子区间最值直接加上要加的值，并将懒标记加上要加的值即可。

如需查询，分为单点查询和区间查询，当前节点被包含在要查询的区间中时直接返回该节点中记录的代表子区间的和即可。

线段树可以维护具有结合性的运算，下文查询以求最小值，修改操作为区间加为例。

3 线段树的函数分析[1，4-5]

3.1 线段树的节点结构

节点的结构如下：

1）所有子节点即该节点代表区间的最小值。

2）需要区间修改时需要一个懒标记。

C++代码如图1所示。

tr数组是线段树本体，对于下标为x的节点，它的左子节点下标为x*2，右子节点下标为x*2+1。

3.2 线段树完成操作所需的函数

3.2.1 建树

线段树递归的去建立节点，对于每个节点，它代表的区间总是它父节点代表的区间的一半，根节点代表的区间为维护的数组的大小。C++代码如图2所示。

其中参数l，r为建立线段树维护数组的区间，x为当前节点编号。

3.2.2 单点修改

线段树单点修改时无须懒标记，只需修改要修改的下标对应节点的值并在回溯时修改父节点即可。这里还涉及懒标记的下放，必须先下放懒标记再递归。C++代码如图3所示。

参数中p是要修改的下标，l、r是当前节点代表的区间，k是要在区间上加的量，x是当前节点的编号。

3.2.3 区间修改

区间修改时只需修改要修改的区间的父节点，将修改记录在懒标记上即可。这里的父节点是必须完全包含在要修改区间内的。同樣需要下放懒标记。C++代码如图4所示。

其中left，right为要修改的区间，其他与单点修改的含义相同。

3.2.4 单点查询

单点查询时需要先将标记下放，因为懒标记只是暂时不将修改落实到子节点，但查询实际值时就需要将修改实际落实到要查询的节点。C++代码如图5所示。