线段树的结构
线段树是一棵二叉树,其结点是一条“线段”——[a,b],它的左儿子和右儿子分别是这条线段的左半段和右半段,即[a, (a+b)/2 ]和[(a+b)/2 ,b]。线段树的叶子结点是长度为1的单位线段[a,a+1]。下图就是一棵根为[1,10]的线段树:
易证一棵以[a,b]为根的线段树结点数是2*(b-a)-1。由于线段树是一棵平衡树,因此一棵以[a,b]为根结点的线段树的深度为log2(2*(b-a))。
线段树中的结点一般采取如下数据结构:
其中a,b分别表示线段的左端点和右端点,Left,Right表示左儿子和右儿子的编号。因此我们可以用一个一维数组来表示一棵线段树:
Tree:array[1..Maxn] of TreeNode;
a,b,Left,Right这4个域是描述一棵线段树所必须的4个量。根据实际需要,我们可以增加其它的域,例如增加Cover域来计算该线段被覆盖的次数,bj域用来表示结点的修改标记(后面将会提到)等等。
线段树的建立
我们可以用一个简单的过程建立一棵线段树。
线段树中的线段