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

1、线段树在算法中的应用作者：朱凯迪作者单位：宁波工程学院Email:摘 要： 计算机信息学竞赛中出现了越来越多的统计，查找，规划，排序，染色等等的题目。平衡二叉树和线段树是两种最常见的解决此类问题的数据结构。可是平衡二叉树有一个缺点，就是变成复杂度很高。我们可以看到在某些题目中，线段树是它的有力替代品。这篇论文主要介绍了线段树的操作，优化以及应用。该论文也会系统地介绍染色问题使用线段树的一般解法。关键词：线段树 数据结构 信息学 算法1. 线段树的定义及特征一棵二叉树，记为T(a, b)，参数a, b表示该结点表示的区间a, b。区间长度b-a记为L。递归定义Ta,

2、b：若L1：a, (a + b) div 2为T的左儿子 (a + b) div 2, b为T的右儿子。若L=1：T为一个叶子结点。表示区间1, 10的线段树表示如图1-1所示：(图1-1)定理1：线段树把区间任意一条线段都分成不超过条线段。证明： 在区间(a, b)中，对于线段(c, d)，如果(c = b)，那么线段在(a, b)中被分为不超过。用归纳法证明，如果是单位区间，最多被分为一段，成立。如果区间(a, b)的左儿子与右儿子成立，那么如果当c = a时，1 若d (a + b) div 2那么相当于该线段被分为它左儿子表示的线段，加上右儿子分该线段，线段数不超过，也不超过，成立。对

3、于d = b的情况证明类似，不在赘述。 在区间(a, b)中，对于任意线段也用归纳法证明。对于单位区间，最多分为一段，成立。若(a, b)的左儿子与右儿子均成立，则对于线段(c, d)1 若d (a + b) div 2则该区间所分该线段等于其右儿子区间所分该线段，线段数小于，成立。3 若1、2均不成立，则此线段在左儿子区间分该线段满足d V.Lson.b Lson为Left Son的缩写，表示左儿子。，分该线段数不超过，而在右儿子区间分该线段满足c = V.Rson.a Rson为Reft Son的缩写，表示右儿子。，分该线段不超过，所以在该区间分该线段不超过，成立。这个结论为线段数能在的时

4、间内完成一条线段的插入、删除、查找等工作提供了理论依据。除了以上性质，线段数还具有以下一些性质：l 线段数是一个平衡树，树的高度为。l 任两个结点要么是包含关系要么没有公共部分，不可能重叠。l 给定一个叶子p，从根到p路径上所有结点代表的区间都包含点p，且其它结点代表的区间都不包含p。2. 线段树的基本存储结构和操作2.1 线段数的基本存储结构线段数的一个结点的最基本存储数据结构如图2-1-1所示：struct Seg int left, right, mid; Seg *lson, *rson;(图2-1-1)也可以用数组模拟二叉树，则结构体中不需要两个指针变量。其中left和right分别

5、表示该结点的左右端点，而mid则是中点。这样就不需要在每次再计算了。而lson和rson分别指向该结点的左儿子和右儿子，如果没有，则为NULL。这只是线段树结点的最基本结构，在解决实际问题时，还需要根据实际情况添加各种需要储存的数据。如ZOJ1610 Count the Colors /onlinejudge/showProblem.do?problemCode=1610，染色问题。下文会具体讲解。中，我建立的线段树结点结构体如图2-1-2所示：struct tree int l, r, col, mid; tree *lc, *rc;(图2-1-2)其

6、中l, r各代表左右端点，mid代表中点，col代表颜色。lc和rc各代表左儿子和右儿子。2.2 线段数的基本操作2.2.1 线段树的建立操作在对线段树进行操作前，我们需要建立起线段树的结构。我们使用结构体数组来保存线段树，这样对于非叶节点，若它在数组中编号为 num，则其左右子节点的编号为 2 * num，2 * num + 1。由于线段树是二分的树型结构，我们可以用递归的方法，从根节点开始来建立一棵线段树。代码如图2-2-1所示：node seg_tree3 * MAXN; /由线段树的性质可知，建树所需要的空间大概是所需处理最长线段长度的 2 倍多，所以需要开 3 倍大小的数组 void

7、 make(int l, int r, int num)/l,r 分别为当前节点的左右端点，num为节点在数组中的编号 seg_treenum.left = l; seg_treenum.right = r; seg_treenum.mid = (l + r) / 2; if (l + 1 != r) /若不为叶子节点，则递归的建立左右子树 make(l, seg_treenum.mid, 2 * num); make(seg_treenum.mid, r, 2 * num + 1); (图2-2-1)对应不同的题目，我们会在线段树节点中添加另外的数据域，并随着线段的插入或删除进行维护，要注意

8、在建树过程中将这些数据域初始化。2.2.2 线段树的插入操作为了在插入线段后，我们能知道哪些节点上的线段被插入（覆盖）过。我们需要在节点中添加一个cover域，来记录当前节点所表示的线段是否被覆盖。这样，在建树过程中，我们需要把每个节点的cover 域置 0；在线段的插入过程中，我们从根节点开始插入，同样采取递归的方法。如果插入的线段完全覆盖了当前节点所代表的线段，则将当前节点的 cover 域置 1 并返回。否则，将线段递归进入当前节点的左右子节点进行插入。代码图2-2-2所示。void insert(int l, int r, int num) /l,r 分别为插入当前节点线段的左右端点，

9、num为节点在数组中的编号 if (seg_treenum.left = l & seg_treenum.right = r)/若插入的线段完全覆盖当前节点所表示的线段 seg_treenum.cover = 1; return; if (r = seg_treenum.mid) /当前节点的右子节点所代表的线段包含插入的线段 insert(l, r, 2 * num +1); else /插入的线段跨越了当前节点所代表线段的中点 insert(l, seg_treenum.mid, 2 * num); insert(seg_treenum.mid, r, 2 * num + 1); (图2-

10、2-2)要注意，这样插入线段时，有可能出现以下这种情况，即先插入线段1,3)，再插入线段1,5)。这样，代表线段1,3)的节点以及代表线段1,5)的节点的 cover 值均为 1，但是在统计时，遇到这种情况，我们可以只统计更靠近根节点的节点，因为这个节点所代表的线段包含了其子树上所有节点所代表的线段。 2.2.3 线段树的删除操作线段树的删除操作跟插入操作不大相同，因为一条线段只有被插入过才能被删除。比如插入一条线段3,10)，则只能删除线段4,6)，不能删除线段7,12)。当删除未插入的线段时，操作返回 false 值。 我们一样采用递归的方法对线段进行删除，如果当前节点所代表的线段未被覆盖

11、，即 cover 值为 0，则递归进入此节点的左右子节点进行删除。而如果当前节点所代表的线段已被覆盖，即 cover 值为 1，则要考虑两种情况。一是删除的线段完全覆盖当前节点所代表的线段，则将当前节点的cover值置0。我们应该递归的在当前节点的子树上所有节点删除线段。另一种情况是删除的线段未完全覆盖当前节点所代表的线段，比如当前节点代表的线段为1,10)，而要删除的线段为4,7)，则删除后剩下线段1,4)和7,10)，我们采用的方法是，将当前节点的cover置0，并将其左右子节点的 cover置 1，然后递归的进入左右子节点进行删除。 删除操作的代码如图2-2-3所示：bool del(i

12、nt l, int r, int num) if (seg_treenum.left + 1 = seg_treenum.right) /删除到叶节点的情况 int f = seg_treenum.f; seg_treenum.f = 0; return f; if (seg_treenum.f = 1) /当前节点不为叶节点且被覆盖 seg_treenum.f = 0; seg_tree2 * num.f = 1; seg_tree2 * num + 1.f = 1; if (r = seg_treenum.mid) return del(l, r, 2 * num + 1); else r

13、eturn del(l, seg_treenum.mid, 2 * num) & del(seg_treenum.mid, r, 2 * num + 1); 图2-2-3相对插入操作，删除操作比较复杂，需要考虑的情况很多，稍有不慎就会出错，在比赛中写删除操作时务必联系插入操作的实现过程，仔细思考，才能避免错误。2.2.4 线段树的统计操作对应不同的问题，线段树会统计不同的数据，比如线段覆盖的长度，线段覆盖连续区间的个数等等。其实现思路不尽相同，我们以下以统计线段覆盖长度为例，简要介绍线段树统计信息的过程。文章之后的章节会讲解一些要用到线段树的题目，并会详细介绍线段树的用法，以及各种信息的统计过

14、程。 对于统计线段覆盖长度的问题，可以采用以下的思路来统计信息，即从根节点开始搜索整棵线段树，如果当前节点所代表的线段已被覆盖，则将统计长度加上当前线段长度。否则，递归进入当前节点的左右子节点进行统计。实现代码图2-2-4所示：int cal(int num) if (seg_treenum.f) return seg_treenum.right seg_treenum.left + 1; if (seg_treenum.left + 1 = seg_treenum.right) /当遍历到叶节点时返回 return 0; return cal(2 * num) + cal(2 * num +

15、 1); (图2-2-4)小结：线段树作为一种数据结构只是解决问题的一个工具，具体的使用方法则非常灵活。以上介绍的仅仅为线段树的基础，在实际应用中，需要针对待解的题目设计节点存储信息，以及修改维护操作等等。下面将由浅及深的介绍线段树的一些应用，其中的一些线段树使用方法值得思考和借鉴。3. 线段树的应用举例3.1 染色问题问题链接：/onlinejudge/showProblem.do?problemCode=1610代码链接：/code/u/XadillaX/ZJU/1610 ACMDIY平台为作者自主开发的一个在

16、线代码库平台。问题大意：输入n个有色线段a,b，问最后每种颜色有多少连续段？（所有数字在0,8000范围内）解题思路：这里是一个结构体：struct treeint l, r, col, mid;tree *lc, *rc;l、r各代表左右端点，mid代表中点，col代表颜色。lc和rc各代表左儿子和右儿子。1. 创建线段树1) 取最小和最大的两个数作为端点，建立线段树。2) 当前节点的两个端点值之差等于一时，此时该节点即位叶子节点，不用再向下分。3) 否则，分裂该节点为a，(a + b) / 2, (a + b) / 2, b;4) 创建线段树时，注意初始化操作。2. 线段树着色（根据不同的

17、题目此操作各不相同，对zju_1610做分析）1) 当前节点的颜色与将要涂的颜色color相同，直接return。2) 当前线段树节点的两个端点和要涂的两个端点正好都相同，则将该节点着为color，然后return。3) 要涂的两个端点在当前节点的两个端点之间时：先将当前节点的颜色向其子节点扩展，然后： 要涂的右端点小于或等于当前节点middle = (a + b) / 2时，向左子节点移动。 要涂的左端点大于或等于当前节点middle = (a + b) / 2时，向右子节点移动。 else （1 ，2）向左右子节点移动。源 代 码：/*File:p1610.cpp*Author:xadil

18、lax*CreatedonMay4,2010,7:20PM*/#include#include#include#include#defineNOCOL-1#defineMULCOL-2usingnamespacestd;structtreeintl,r,col,mid;tree*lc,*rc;tree*root;intn,l,r,col,i;intcolor8001,cnt8001;tree*init(intl,intr)/建立一棵线段树tree*rst;rst=(tree*)malloc(sizeof(tree);rst-l=l,rst-r=r,rst-mid=(l+r)/2,rst-col

19、=NOCOL;if(r-l=1)rst-lc=NULL;rst-rc=NULL;elserst-lc=init(rst-l,rst-mid);rst-rc=init(rst-mid,rst-r);returnrst;voidput(tree*p,intl,intr,intcol)if(p-l=l&p-r=r)p-col=col;return;if(p-col!=MULCOL)p-lc-col=p-col;p-rc-col=p-col;p-col=MULCOL;if(lmid&rp-mid)put(p-lc,l,p-mid,col);put(p-rc,p-mid,r,col);elseif(p-

20、midrc,l,r,col);elseput(p-lc,l,r,col);voidcal(tree*p,int*color)inti;if(p-col=MULCOL)cal(p-lc,color);cal(p-rc,color);elseif(p-col!=NOCOL)for(i=p-l;ir;i+)colori=p-col;elsefor(i=p-l;ir;i+)colori=NOCOL;free(p);intmain()while(scanf(%d,&n)!=EOF)root=init(0,8000);memset(color,0,sizeof(color);memset(cnt,0,si

21、zeof(cnt);while(n-)scanf(%d%d%d,&l,&r,&col);put(root,l,r,col);cal(root,color);if(color0!=NOCOL)cntcolor0+;for(i=1;i=7999;i+)if(colori!=NOCOL&colori!=colori-1)cntcolori+;for(i=0;i0)printf(%d%dn,i,cnti);printf(n);return0;3.2 城市景观问题链接：/JudgeOnline/problem?id=3277问题大意：如图所示，在一条水平线上有 N

22、个建筑物，建筑物都是长方形的，且可以互相遮盖。给出每个建筑物的左右坐标值Ai,Bi 以及每个建筑物的高度Hi，需 要计算出这些建筑物总共覆盖的面积。题目数据范围： 建筑物个数 N：1 = N = 40000 建筑物左右坐标值Ai, Bi：1 = Ai,Bi = 109 建筑物的高度 Hi：1 = Hi = 109解题思路：因为区间最大到10的9次方，开这么大的空间内存肯定不够，所以要离散化，用map存入然后用iterator遍历得到的有序序列存入vector。然后以vector的下标建立线段树，统计时若结点不是叶子结点，则它的值为左右孩子的值之和，否则返回 底*高 。源 代 码： 此源代码来自

23、文献参考中的第七项。#include #include #include using namespace std;typedef struct nod int left,right,mid;long long h;bool cover;node,*nd;typedef struct plong long start,end,hi;point;/ 元素个数上限和存储数组const int MAX_NUM=; /第一次交re,干脆开个大的node seg_tree3*MAX_NUM+1;point list40005;map my_map;map:iterator it;vector vec;/

24、创建 , l为左端点，r为右端点，num为在数组中的编号void make(int l,int r,int num)seg_treenum.left=l;seg_treenum.right=r;seg_treenum.h=0;seg_treenum.mid= (l+r)/2;if( l+1 != r )make(l,seg_treenum.mid,2*num);make(seg_treenum.mid,r,2*num+1);/ 插入操作，参数意义同上void Insert(int l,int r,int num ,long long &hi)if( seg_treenum.left=l & s

25、eg_treenum.right=r )if(seg_treenum.hhi) seg_treenum.h=hi;return ;if( r=seg_treenum.mid )Insert(l,r,2*num+1,hi);else Insert(l,seg_treenum.mid,2*num,hi);Insert(seg_treenum.mid,r,2*num+1,hi);/统计操作long long cal(long long hi,int num)if(hiseg_treenum.h) seg_treenum.h=hi;if( seg_treenum.left+1 = seg_treenu

26、m.right )return seg_treenum.h*( vec seg_treenum.right - vec seg_treenum.left );return cal( seg_treenum.h , 2*num ) + cal( seg_treenum.h , 2*num+1 );int main()int T,t=1;cinT;long long a,b,h;for(int i=0;iabh;my_mapa=0;my_mapb=0;listi.start=a; listi.end=b; listi.hi=h;vec.push_back(0); /压入一个元素使vec从下标1开始

27、有效for( it=my_map.begin(); it!=my_map.end();+it )it-second=t+;vec.push_back( it-first );vec.push_back( vecvec.size()-1 +1 ); /将离散化之后的元素按顺序压入向量make(1,my_map.size()+1,1);for(int i=0;iT;+i)Insert( my_map listi.start , my_map listi.end ,1 , listi.hi );coutcal( seg_tree1.h ,1 )endl;return 0;4. 线段树的应用总结线段树

28、是一种高效的数据结构。它的思想就是分治，非常基本也非常强大。在学习线段树的过程中，要时刻记住，线段树只是一种解题的工具，学习线段树只是学习一种解题的思维，就像图论中的 BFS 广度优先搜索，俗称暴力搜索。 一样。至于在具体的题目中如何去运用这个工具，则灵活的去建树并维护相关信息。这也需要在平时进行积累，做题时才能应用熟练。5. 线段树的练习题目推荐 以下题目是各 OJ 上比较有名的线段树题目 Whu OnlineJudge /oak 题目号： 1071 1224 1361 1344 Pku OnlineJudge

29、/JudgeOnline 题目号 3225 2482 1177 1029 2182 2750 2104 2528 2828 2777 2886 2761 Zju OnlineJudge 题目号 2301 1128 1659 2112参考文献1岳云涛.浅谈线段数在信息学竞赛中的应用J.2林涛.线段数的应用J,2004.3刘汝佳, 黄亮.算法艺术与信息学竞赛M. 北京：清华大学出版社，2004.4Thomas H.Cormen, Charles E.Leiserson, Ronald L.Rivest et al. Introduction to AlgorithmsM. 2nd Edition. America: The MIT Press, 2001.5廖劲宇. pku 3277 (线段树+离散化)OL. /liaojinyu282/archive/2010/01/16/.aspx, 2010.6朱凯迪. ZOJ1610 Cou