新手从零基础建站初级网站建设,商业广告公司排名,免费word模板,discuz与wordpress线段树的结构 线段树是一棵二叉树#xff0c;其结点是一条“线段”——[a,b]#xff0c;它的左儿子和右儿子分别是这条线段的左半段和右半段#xff0c;即[a, (ab)/2 ]和[(ab)/2 ,b]。线段树的叶子结点是长度为1的单位线段[a,a1]。下图就是一棵根为[1,10]的线段树#xff1…线段树的结构 线段树是一棵二叉树其结点是一条“线段”——[a,b]它的左儿子和右儿子分别是这条线段的左半段和右半段即[a, (ab)/2 ]和[(ab)/2 ,b]。线段树的叶子结点是长度为1的单位线段[a,a1]。下图就是一棵根为[1,10]的线段树 易证一棵以[a,b]为根的线段树结点数是2*(b-a)-1。由于线段树是一棵平衡树因此一棵以[a,b]为根结点的线段树的深度为log2(2*(b-a))。 线段树中的结点一般采取如下数据结构 其中a,b分别表示线段的左端点和右端点LeftRight表示左儿子和右儿子的编号。因此我们可以用一个一维数组来表示一棵线段树 Tree:array[1..Maxn] of TreeNode; a,b,Left,Right这4个域是描述一棵线段树所必须的4个量。根据实际需要我们可以增加其它的域例如增加Cover域来计算该线段被覆盖的次数bj域用来表示结点的修改标记后面将会提到等等。 线段树的建立 我们可以用一个简单的过程建立一棵线段树。 线段树中的线段插入和删除 增加一个Cover的域来计算一条线段被覆盖的次数即数据结构变为 因此在MakeTree的时候应顺便把Cover置0。 线段的插入 插入一条线段[c,d] 线段的删除 删除一条线段[c,d] 线段树的简单应用 掌握了线段树的建立插入和删除这3条操作就能用线段树解决一些最基本的统计问题了。例如给出一系列线段[a,b] (0 a b 10000)覆盖在数轴上然后求该数轴上共有多少个单位长度[k,k1]被覆盖了。我们便可以在读入一系列线段[a,b]的时候同时调用过程Insert(1)。等所有线段都插入完后就可以进行统计了 像这样的基本静态统计问题线段树是可以很方便快捷地解决的。但是我们会留意到如果处理一些动态统计问题比如说一些需要用到删除和修改的统计困难就出现了。 『例1』 在数轴上进行一系列操作。每次操作有两种类型一种是在线段[a,b]上涂上颜色另一种将[a,b]上的颜色擦去。问经过一系列的操作后有多少条单位线段[k,k1]被涂上了颜色。 这时我们就面临了一个问题——线段的删除。但线段树中线段的删除只能是把已经放入的线段删掉例如我们没有放置[3,6]这条线段删除[3,6]就是无法做到的了。而这道题目则不同例如在[1,15]上涂了颜色我们可以把[4,9]上的颜色擦去但线段树中只是插入了[1,15]这条线段要删除[4,9]这条线段显然是做不到的。因此我们有必要对线段树进行改进。 线段树的改进 【关键词状态下沉标志向下扩散】 用回刚刚那个例子。给[1,15]涂上色后再把[4,9]的颜色擦去。很明显[1,15]这条线段已经不复存在只剩下[1,4]和[9,15]所以我们必须对线段树进行修改才能使它符合改变了的现实。我们不难想到把[1,15]这条线段删去再插入线段[1,4]和[9,15]。但事实上并非如此简单。如下图: 若先前我们已经插入了线段[8,11][1,8]。按上面的做法只把[1,15]删去然后插入[1,4][9,15]的话[1,8][8,11]这两条线段并没有删去但明显与实际不符了。于是[1,8][8,11]也要修改。这时疑问就来了。若以线段[1,15]为根的整棵线段树中的所有结点之前都已经插入过即我们曾经这样涂过颜色[1,2],[2,3]……[14,15],[1,3],[3,5],……,[13,15],[1,5]…………[1,15]。然后把[1,15]上的颜色擦去。那么整个线段树中的所有结点的状态就都与实际不符了全都需要修改。修改的复杂度就是线段树的结点数即2*(15-1)28。如果不是[1,15]这样的小线段而是[1,30000]这样的线段一个擦除动作就需要O(59998)的复杂度去修改显然效率十分低比直接模拟的O(30000)还差。 为了解决这个问题我们给线段树的每一个结点增加一个标记域以下用bj来表示标记域。增加一个标记域有什么用呢如下图 以[1,5]为根的整棵线段树的全部结点都已涂色。现把[1,5]上的颜色擦去。则整棵线段树的结点的状态都与实际不符了。可是我们并不一定要对所有结点都进行修改因为有些结点以后可能根本不会有被用到的时候。例如我们做完擦去[1,5]的操作之后只是想询问[3,5]是否有涂上颜色。那么我们对[1,2][2,3],[1,3],[3,4],[4,5]等线段的修改就变成无用功了。为了避免无用功的出现我们引入标记域bj。具体操作如下 1、擦去线段[a,b]之后给它的左儿子和右儿子都做上标记令它们的bj-1。 2、每次访问一条线段首先检查它是否被标记若其bj-1则进行如下操作 ①将该线段的状态改为未被覆盖并把该线段设为未被标记bj0。 ②把该线段的左右儿子都设为被标记bj-1。 对线段[1,5]进行了这样的操作后就不需要对整棵线段树都进行修改了。原理很简单。以线段[3,4]为例。若以后有必要访问[3,4]则必然先访问到它的父亲[3,5]而[3,5]的bj-1因此进行①、②的操作后[3,5]的状态变为未被覆盖并且把他的标记传递给了他的儿子——[3,4]和[4,5]。接着访问[3,4]的时候它的bj-1我们又把[3,4]的状态变为未被覆盖。可见标记会顺着访问[3,4]的路一直传递到[3,4]使得我们知道要对[3,4]的状态进行修改避免了错误的产生。同时当我们需要用到[3,4]的时候才会进行修改如果根本不需要用它修不修改都无所谓了并不会影响程序的正确性。因此这种方法在保持了正确性的同时有避免了无意义的操作提高了程序的效率。 进行标记更新的代码如下 每次访问线段[a,b]之前首先检查它是否被标记如果是则调用过程Clear进行状态修改。这样做只是在访问的时候顺便进行修改复杂度是O(1)程序效率依然很高。 于是引入标记域后本题中插入和删除的过程大致如下 插入过程 Insert 1、若该线段被标记则调用Clear过程 2、若线段状态为被涂色则退出过程线段已被涂色无需再插入它或它的子线段 3、若涂色的区域覆盖了该线段则该线段的状态变为被涂色并退出过程 4、若涂色的区域与该线段的左半截的交集非空则调用左儿子的插入过程 5、若涂色的区域与该线段的右半截的交集非空则调用右儿子的插入过程 删除过程 Delete 1、若该线段被标记则退出过程该线段已被赋予被擦除的“义务”无需再次赋予 2、若擦除的区域覆盖了该线段则该线段的状态变为未被涂色并将其左右儿子都做上标记退出过程 3、若该线段的状态为被涂色则 ① 该线段状态变为未被涂色 ② 将其左右儿子做上标记 ③ 插入线段[a,c]和[d,b] 4、若该线段的状态为未被涂色则 ①若擦除区域与该线段的左半截的交集非空则调用左儿子的擦除过程 ②若擦除区域与该线段的右半截的交集非空则调用右儿子的擦除过程 归纳一下标记域的思想及如何使用。如果我们对整条线段[a,b]进行操作的话我们就可以只是给[a,b]的左右儿子做上标记而无需对以[a,b]为根的整棵子树中的所有结点进行修改。原理就是对下面的所有结点[c,d]都有[c,d] [a,b]因此[a,b]状态的改变也就代表了[c,d]状态的改变。 本着这个思想标记域的使用形式并不是固定的而是多样的具体形式如何要视题目而定但只要理解了它的思想总能想到如何确定作标记的方式维持线段树的高效。
