线段树在算法中的应用[朱凯迪]

宁波工程学院学年论文-1-线段树在算法中的应用作者：朱凯迪作者单位：宁波工程学院Email:[e-mail]摘要：计算机信息学竞赛中出现了越来越多的统计，查找，规划，排序，染色等等的题目。平衡二叉树和线段树是两种最常见的解决此类问题的数据结构。可是平衡二叉树有一个缺点，就是变成复杂度很高。我们可以看到在某些题目中，线段树是它的有力替代品。这篇论文主要介绍了线段树的操作，优化以及应用。该论文也会系统地介绍染色问题使用线段树的一般解法。关键词：线段树数据结构信息学算法1.线段树的定义及特征一棵二叉树，记为T(a,b)，参数a,b表示该结点表示的区间[a,b]。区间长度b-a记为L。递归定义T[a,b]：若L1：[a,(a+b)div2]为T的左儿子[(a+b)div2,b]为T的右儿子。若L=1：T为一个叶子结点。表示区间[1,10]的线段树表示如图1-1所示：(图1-1)宁波工程学院学年论文-2-定理1：线段树把区间任意一条线段都分成不超过Llog2条线段。证明：①在区间(a,b)中，对于线段(c,d)，如果(c=a)或(d=b)，那么线段在(a,b)中被分为不超过)log(ab。用归纳法证明，如果是单位区间，最多被分为一段，成立。如果区间(a,b)的左儿子与右儿子成立，那么如果当c=a时，1．若d=(a+b)div2那么相当与其左儿子分该线段，所分该线段树不超过)2)log((adivba，即不超过)log(ab，成立。2．若d(a+b)div2那么相当于该线段被分为它左儿子表示的线段，加上右儿子分该线段，线段数不超过)2)(log(1divbab，也不超过)log(ab，成立。对于d=b的情况证明类似，不在赘述。②在区间(a,b)中，对于任意线段也用归纳法证明。对于单位区间，最多分为一段，成立。若(a,b)的左儿子与右儿子均成立，则对于线段(c,d)1．若d=(a+b)div2则该区间所分该线段等于其左儿子区间所分该线段，线段数小于)log(2)2)(log(abadivbab，成立。2．若c(a+b)div2则该区间所分该线段等于其右儿子区间所分该线段，线段数小于)log(2)2)(log(abdivbab，成立。3．若1、2均不成立，则此线段在左儿子区间分该线段满足dV.Lson.b1，分该线段数不超过)2)(log(divbab，而在右儿子区间分该线段满足c=V.Rson.a2，分该线段不超过)12)(log(divbab，所以在该区间分该线段不超过)log(2ab，成立。这个结论为线段数能在)(logLO的时间内完成一条线段的插入、删除、查找等工作提供了理论依据。除了以上性质，线段数还具有以下一些性质：线段数是一个平衡树，树的高度为Nlog。任两个结点要么是包含关系要么没有公共部分，不可能重叠。给定一个叶子p，从根到p路径上所有结点代表的区间都包含点p，且其它结点代表的区间都不包含p。2.线段树的基本存储结构和操作1Lson为LeftSon的缩写，表示左儿子。2Rson为ReftSon的缩写，表示右儿子。宁波工程学院学年论文-3-2.1线段数的基本存储结构线段数的一个结点的最基本存储数据结构如图2-1-1所示：(图2-1-1)也可以用数组模拟二叉树，则结构体中不需要两个指针变量。其中left和right分别表示该结点的左右端点，而mid则是中点。这样就不需要在每次再计算了。而lson和rson分别指向该结点的左儿子和右儿子，如果没有，则为NULL。这只是线段树结点的最基本结构，在解决实际问题时，还需要根据实际情况添加各种需要储存的数据。如[ZOJ]1610CounttheColors3中，我建立的线段树结点结构体如图2-1-2所示：(图2-1-2)其中l,r各代表左右端点，mid代表中点，col代表颜色。lc和rc各代表左儿子和右儿子。2.2线段数的基本操作2.2.1线段树的建立操作在对线段树进行操作前，我们需要建立起线段树的结构。我们使用结构体数组来保存线段树，这样对于非叶节点，若它在数组中编号为num，则其左右子节点的编号为2*num，2*num+1。由于线段树是二分的树型结构，我们可以用递归的方法，从根节点开始来建立一棵线段树。代码如图2-2-1所示：3=1610，染色问题。下文会具体讲解。structSeg{intleft,right,mid;Seg*lson,*rson;};structtree{intl,r,col,mid;tree*lc,*rc;};宁波工程学院学年论文-4-(图2-2-1)对应不同的题目，我们会在线段树节点中添加另外的数据域，并随着线段的插入或删除进行维护，要注意在建树过程中将这些数据域初始化。2.2.2线段树的插入操作为了在插入线段后，我们能知道哪些节点上的线段被插入（覆盖）过。我们需要在节点中添加一个cover域，来记录当前节点所表示的线段是否被覆盖。这样，在建树过程中，我们需要把每个节点的cover域置0；在线段的插入过程中，我们从根节点开始插入，同样采取递归的方法。如果插入的线段完全覆盖了当前节点所代表的线段，则将当前节点的cover域置1并返回。否则，将线段递归进入当前节点的左右子节点进行插入。代码图2-2-2所示。nodeseg_tree[3*MAXN];//由线段树的性质可知，建树所需要的空间大概是所需处理最长线段长度的2倍多，所以需要开3倍大小的数组voidmake(intl,intr,intnum){//l,r分别为当前节点的左右端点，num为节点在数组中的编号seg_tree[num].left=l;seg_tree[num].right=r;seg_tree[num].mid=(l+r)/2;if(l+1!=r){//若不为叶子节点，则递归的建立左右子树make(l,seg_tree[num].mid,2*num);make(seg_tree[num].mid,r,2*num+1);}宁波工程学院学年论文-5-(图2-2-2)要注意，这样插入线段时，有可能出现以下这种情况，即先插入线段[1,3)，再插入线段[1,5)。这样，代表线段[1,3)的节点以及代表线段[1,5)的节点的cover值均为1，但是在统计时，遇到这种情况，我们可以只统计更靠近根节点的节点，因为这个节点所代表的线段包含了其子树上所有节点所代表的线段。2.2.3线段树的删除操作线段树的删除操作跟插入操作不大相同，因为一条线段只有被插入过才能被删除。比如插入一条线段[3,10)，则只能删除线段[4,6)，不能删除线段[7,12)。当删除未插入的线段时，操作返回false值。我们一样采用递归的方法对线段进行删除，如果当前节点所代表的线段未被覆盖，即cover值为0，则递归进入此节点的左右子节点进行删除。而如果当前节点所代表的线段已被覆盖，即cover值为1，则要考虑两种情况。一是删除的线段完全覆盖当前节点所代表的线段，则将当前节点的cover值置0。我们应该递归的在当前节点的子树上所有节点删除线段。另一种情况是删除的线段未完全覆盖当前节点所代表的线段，比如当前节点代表的线段为[1,10)，而要删除的线段为[4,7)，则删除后剩下线段[1,4)和[7,10)，我们采用的方法是，将当前节点的cover置0，并将其左右子节点的cover置1，然后递归的进入左右子节点进行删除。删除操作的代码如voidinsert(intl,intr,intnum){//l,r分别为插入当前节点线段的左右端点，num为节点在数组中的编号if(seg_tree[num].left==l&&seg_tree[num].right==r){//若插入的线段完全覆盖当前节点所表示的线段seg_tree[num].cover=1;return;}if(r=seg_tree[num].mid)//当前节点的左子节点所代表的线段包含插入的线段insert(l,r,2*num);elseif(l=seg_tree[num].mid)//当前节点的右子节点所代表的线段包含插入的线段insert(l,r,2*num+1);else{//插入的线段跨越了当前节点所代表线段的中点insert(l,seg_tree[num].mid,2*num);insert(seg_tree[num].mid,r,2*num+1);}｝宁波工程学院学年论文-6-图2-2-3所示：图2-2-3相对插入操作，删除操作比较复杂，需要考虑的情况很多，稍有不慎就会出错，在比赛中写删除操作时务必联系插入操作的实现过程，仔细思考，才能避免错误。2.2.4线段树的统计操作对应不同的问题，线段树会统计不同的数据，比如线段覆盖的长度，线段覆盖连续区间的个数等等。其实现思路不尽相同，我们以下以统计线段覆盖长度为例，简要介绍线段树统计信息的过程。文章之后的章节会讲解一些要用到线段树的题目，并会详细介绍线段树的用法，以及各种信息的统计过程。对于统计线段覆盖长度的问题，可以采用以下的思路来统计信息，即从根节点开始搜索整棵线段树，如果当前节点所代表的线段已被覆盖，则将统计长度加上当前线段长度。否则，递归进入当前节点的左右子节点进行统计。实现代码图2-2-4所示：booldel(intl,intr,intnum){if(seg_tree[num].left+1==seg_tree[num].right){//删除到叶节点的情况intf=seg_tree[num].f;seg_tree[num].f=0;returnf;}if(seg_tree[num].f==1){//当前节点不为叶节点且被覆盖seg_tree[num].f=0;seg_tree[2*num].f=1;seg_tree[2*num+1].f=1;}if(r=seg_tree[num].mid)returndel(l,r,2*num);elseif(l=seg_tree[num].mid)returndel(l,r,2*num+1);elsereturndel(l,seg_tree[num].mid,2*num)&&del(seg_tree[num].mid,r,2*num+1);}宁波工程学院学年论文-7-(图2-2-4)小结：线段树作为一种数据结构只是解决问题的一个工具，具体的使用方法则非常灵活。以上介绍的仅仅为线段树的基础，在实际应用中，需要针对待解的题目设计节点存储信息，以及修改维护操作等等。下面将由浅及深的介绍线段树的一些应用，其中的一些线段树使用方法值得思考和借鉴。3.线段树的应用举例3.1染色问题问题链接：=1610代码链接：问题大意：输入n个有色线段[a,b]，问最后每种颜色有多少连续段？（所有数字在[0,8000]范围内）解题思路：这里是一个结构体：l、r各代表左右端点，mid代表中点，col代表颜色。lc和rc各代表左儿子和右儿子。1.创建线段树1)取最小和最大的两个数作为端点，建立线段树。2)当前节点的两个端点值之差等于一时，此时该节点即位叶子节点，不用再向下分。3)否则，分裂该节点为[a，(a+b)/2],[(a+b)/2,b];4)创建线段树时，注意初始化操作。4ACMDIY平台为作者自主开发的一个在线代码库平台。intcal(intnum){if(seg_tree[num].f)returnseg_tree[num].right–seg_tree[num].left+1;if(seg_tree[num].left+1==seg_tree[num].right)//当遍