IOI2004 国家集训队论文 林涛
第 1 页 共 9 页
线段树的应用
广西柳铁一中 林涛
【摘要】
在竞赛解题中,常遇到与区间有关的操作,比如统计若干矩形并的面积,记
录一个区间的最值、总量,并在区间的插入、删除和修改中维护这些最值、总量。
线段树拥有良好的树形二分结构,能够高效的完成这些操作,本文将介绍
线段树的各种操作以及一些推广。
本文通过 3 个例子:《蛇》 、《空心长方体》、 《战场统计系统》,讲述线
段树中基本的插入、删除、查找操作,和不规则的修改和删除操作,以及到二维
的推广。
关键字:线段树 二分 子树收缩 叶子释放 面积树
【正文】
1. 线段树的定义及特征
定义 1:线段树
一棵二叉树,记为 T (a,b),参数 a,b 表示该节点表示区间[a,b]。区间的长度
b-a 记为 L。递归定义 T[a,b]:
若 L>1 :[a, (a+b) div 2]为 T的左儿子
[(a+b) div 2,b]为 T 的右儿子。
若L=1 :T 为一个叶子节点。
表示区间[1, 10]的线段树表示如下:
[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:线段树把区间上的任意一条线段都分成不超过 2logL 条线段
证明:(1)在区间(a,b)中,对于线段(c,d),如果(c<=a) 或 (d>=b),那么线段在
(a,b)中被分为不超过 log(b-a)。
用归纳法证明,如果是单位区间,最多被分为一段,成立。
如果区间(a,b)的左儿子与右儿子成立,那么如果当 c<=a 时,
1.若 d<=(a+b)div2 那么相当与其左儿子分该线段,所分该线段数树不
超过 log((a+b)div 2-a),即不超过 log(b-a),成立。