线段树
线段树
•
在一类问题中，我们需要经常处理可以映
射在一个坐标轴上的一些固定线段，例如
说映射在 OX 轴上的线段。由于线段是可以
互相覆盖的，有时需要动态地取线段的并，
例如取得并区间的总长度，或者并区间的
个数等等。一个线段是对应于一个区间的，
因此线段树也可以叫做区间树。
线段树的构造思想
•
线段树是一棵二叉树，树中的每一个结点
表示了一个区间 [a,b] 。每一个叶子节点表
示了一个单位区间。对于每一个非叶结点
所表示的结点 [a,b] ，其左儿子表示的区间
为 [a,(a+b)/2] ，右儿子表示的区间为 [(a+b)
/2,b] 。
[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]
线段树的运用
•
线段树的每个节点上往往都增加了一些其
他的域。在这些域中保存了某种动态维护
的信息，视不同情况而定。这些域使得线
段树具有极大的灵活性，可以适应不同的
需求。
