2、单位线段[a,a+1]。1线段树※1.3线段的插入和删除可增加一个Cover域来计算一条线段被覆盖的次数：TypeTreeNode=Recorda,b,Left,Right,Cover:LongintEnd插入一条线段[c,d]ProcedureInsert(Num)BeginIf(cthenInsert(Tree[Num].Right)End1线段树删除一条线段[c,d]
3、ProcedureDelete(Num)BeginIf(cthenDelete(Tree[Num].Right)End1线段树※1.4线段树的简单应用线段树能解决一些最基本的统计问题。但是如果处理一些需要进行修改的动态统计问题，困难就出现了。例1在数轴上进行一系列操作。每次操作有两种类型，一种是在线段[a,b]上涂上颜色，另一种将[a,b]上的颜色擦去。问经过一系列的操作后
4、，有多少条单位线段[k,k+1]被涂上了颜色。1线段树线段树中线段的删除只能把已经放入的线段删掉。而在这道题目中，若给线段[1,15]涂了颜色，可以把[4,9]上的颜色擦去。但线段树中只是插入了[1,15]这条线段，要删除[4,9]这条线段显然是做不到的。因此，我们有必要对线段树进行改进。1线段树※1.5线段树的改进不难想到把[1,15]这条线段删去，再插入线段[1,4]和[9,15]。但事实上并非如此简单。如下图：若先前已插入了线段[1,8]，[8,11]。按上面的做法，只把[1,15]删去，然后插入[1,4]，[9,15]的话，[1,8]，[8,11]这两条线段并没有删去，很明
5、显是与实际不符的。于是[1,8]，[8,11]也要修改。但若出现以下这种情况：1线段树以线段[1,15]为根的整棵线段树中的所有结点之前都已经插入过，即我们曾经这样涂过颜色：[1,2],[2,3]，……，[14,15],[1,3],[3,5],……,[13,15],[1,5]，…………，[1,15]。然后把[1,15]上的颜色擦去。那么整个线段树中的所有结点的状态就都与实际不符了，全都需要修改。修改的复杂度就是线段树的结点数。线段稍长复杂度就很高了。1线段树为了解决这个问题，我们为每个结点增加一个标记域bj。①将该线段的状态改为未被覆盖，并把该线段设为未被标记，bj=0。②把该线段
6、的左右儿子都设为被标记，bj=-1。1、在擦去线段[a,b]之后，给它的左儿子和右儿子都做上标记，令它们的bj=-1。而不需要对整棵树进行修改。2、以后每次访问某条线段，首先检查它是否被标记，若被标记，则进行如下操作：这样做的原理很简单，以右图为例：1线段树把线段[1,5]擦去后，给[1,3]，[3,5]加上标记。若以后我们需要用到线段[3,4]，就必须先访问[3,5]，因为[3,5]被标记，我们访问它之后标记就会传递给[3,4]和[4,5]。[3,4]就给标记上了。也就是说，标记会顺着访问[3,4]的路径一直传递下去。bj＝-1bj＝-1bj＝-1bj＝-1所以当我们需要用到下面
7、的某条线段时，标记就会传到它那里去，使它得到更新，避免错误的发生。而对于那些以后用不到的线段，就没有更新的必要了，因此我们也不会访问到它和更新它，这样就避免了无用功的产生，提高了程序效率。bj＝01线段树进行标记更新的代码如下：ProcedureClear(Num)BeginTree[Num].Cover←0Tree[Num].bj←0Tree[Tree[Num].Left].bj←-1Tree[Tree[Num].Right].bj←-1End在访问编号为Num的线
