王逸芳，张子牛，齐庆磊

(南阳师范学院计算机科学与技术学院，南阳 453200)

0 引言

随着国家铁路运输事业的快速发展，列车已经成为人们生活中一种十分重要的出行方式。快速、准确的车票查询系统能够给人们带来良好的乘车体验。由于一条铁路线路上站点的数量，乘客从各站点上下车的时间，乘客购买车票的时间等因素都会成为影响车票查询结果的因素，设计和实现快速高效的车票查询系统面临着诸多挑战。

线段树[1-2]作为一种特殊的二叉树，目前已经得到广泛应用，有效解决了动态区间求最值[3]、范围查询[4]，高效内存划分[5]、求矩形面积[6]等问题。线段树的每个节点表示一个区间，存储区间信息。每个节点的孩子节点对该节点的区间进行分割。在线段树中，与叶子节点对应的区间为最小区间。最小区间是指不能再分或者无需再分的区间。线段树具有如下性质：

(1)线段树是一棵平衡二叉树，树的高度为logN，N为线段树中的节点数量。

(2)线段树把区间上的任意一条长度为N的线段都分为不大于2logN条线段的并。

(3)任两个节点可以是包含关系，也可以是没有相同结点关系，不可能有重叠的情况，每层节点的区间的并即为整个区间。

(4)给定一个叶子结点p，从根到p路径上全部节点代表的区间都包括点p，且其他节点代表的区间都不包括点p。

本文将线段树用于火车票管理系统中。每个节点表示某两个车站之间的区域。根节点表示始发站和终点站之间的区域。……