浅谈线段树在信息学竞赛中的应用.PDF

《浅谈线段树在信息学竞赛中的应用》 武汉大学 岳云涛 浅谈线段树在信息学竞赛中的应用 岳云涛 yyt @ cominde Wuhan University 第 1 页 / 共 20 页 《浅谈线段树在信息学竞赛中的应用》 武汉大学 岳云涛 【摘要】 本文介绍了一种高效的基于分治思想的数据结构——线段树，具体讲解了线 段树的建树，查找，删除，统计等基本操作。并结合了一些例题深入研究了线段 树的基本性质和线段树的应用方法。文章最后给出了一些线段树的练习题目。 【关键词】数据结构 二叉树 线段树 【目录】 引言3 1 线段树3 1.1 线段树的基本结构3 1.2 线段树的性质4 1.3 线段树的基本存储结构和操作4 2 线段树的初级应用9 2.1 例题：City Horizon9 2.2 例题 Joseph Problem 12 3 线段树的进阶应用15 3.1 例题 Frequent Values 15 3.2 例题 K-th Number 17 4 线段树的一些推广应用17 4.1 多维线段树17 4.2 线段树与其他数据结构的组合18 5 线段树应用总结19 6 线段树练习题目推荐19 第 2 页 / 共 20 页 《浅谈线段树在信息学竞赛中的应用》 武汉大学 岳云涛 【正文】 引言 在信息学竞赛中，我们经常会碰到一些跟区间有关的问题，比如给一些区 间线段求并区间的长度，或者并区间的个数等等。这些问题的描述都非常简 单，但是通常情况下数据范围会非常大，而朴素方法的时间复杂度过高，导致 不能在规定时间内得到问题的解。这时，我们需要一种高效的数据结构来处理 这样的问题，在本文中，我们介绍一种基于分治思想的数据结构－－线段树。 1 线段树 1.1 线段树的基本结构 线段树是一种二叉树形结构，属于平衡树的一种。它将线段区间组织成树 形的结构，并用每个节点来表示一条线段。一棵[1,10)的线段树的结构如图 1.1 所示： [1,10) [1,5) [5,10) [1,3) [3,5) [5,7) [7,10) [1,2) [2,3) [3,4) [4,5) [5,6) [6,7) [7,8) [8,10) [8,9) [9,10) 图1.1 线段树的结构 可以看到，线段树的每个节点表示了一条前闭后开，即[a,b)的线段，这样表示 的好处在于，有时候处理的区间并不是连续区间，可能是离散的点，如数组 等。这样就可以用[a,a＋1)的节点来表示一个数组的元素，做到连续与离散的统 一。 第 3 页 / 共 20 页 《浅谈线段树在信息学竞赛中的应用》 武汉大学 岳云涛 由图1.1 可见，线段树的根节点表示了所要处理的最大线段区间，而叶节点 则表示了形如[a,a+1)的单位区间。对于每个非叶节点（包括根节点）所表示的区 间[s,t)，令