线段树在算法中的应用

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

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

3、该线段，线段数不超过1 + log(b (a + b)div2)，也不超过 log(b a)，成立。对于d = b的情况证明类似，不在赘述。在区间(a, b)中，对于任意线段也用归纳法证明。对于单位区间，最多分为一段，成立。若(a, b)的左儿子与右儿子均成立，则对于线段(c, d)若d= (a +b) div 2则该区间所分该线段等于其左儿子区间所分该线 段，线段数小于log(b (a + b)div2 a) (a + b) div 2则该区间所分该线段等于其右儿子区间所分该线 段，线段数小于log(b (a + b)div2) V.Lson.bi，分 该线段数不超过log(b (a + b

4、)div2)，而在右儿子区间分该线段满足 c = V.Rson.a2，分该线段不超过log(b (a + b)div2 1)，所以在该 区间分该线段不超过2 log(b a)，成立。这个结论为线段数能在O(logL)的时间内完成一条线段的插入、删除、查找等工作提 供了理论依据。除了以上性质，线段数还具有以下一些性质：线段数是一个平衡树，树的高度为log N。任两个结点要么是包含关系要么没有公共部分，不可能重叠。给定一个叶子p，从根到p路径上所有结点代表的区间都包含点p，且其它结点代 表的区间都不包含p。线段树的基本存储结构和操作Lson为Left Son的缩写，表示左儿子。Rson为Reft

5、Son的缩写，表示右儿子。2.1线段数的基本存储结构线段数的一个结点的最基本存储数据结构如图2-1-1所示：struct Seg（int left, right, mid;Seg *lson, *rson;；（图 2-1-1）也可以用数组模拟二叉树，则结构体中不需要两个指针变量。其中left和right分别表示该结点的左右端点，而mid则是中点。这样就不需要在每次 再计算了。而lson和rson分别指向该结点的左儿子和右儿子，如果没有，则为NULL。这只是线段树结点的最基本结构，在解决实际问题时，还需要根据实际情况添加各种需 要储存的数据。如ZOJ1610 Count the Colors H

6、YPERLINK /onlinejudge/showProblem.do7problemCodeT610%ef%bc%8c%e6%9f%93%e8%89%b2%e9%97%ae%e9%a2%98%e3%80%82%e4%b8%8b%e6%96%87%e4%bc%9a%e5%85%b7%e4%bd%93%e8%ae%b2%e8%a7%a3%e3%80%82 /onlinejudge/showProblem.do7problemCodeT610，染色问题。下文会具体讲解。中，我建立的线段树结点结构体如图2-1-2所 示：struct tree（int l, r, col, mid;tree *lc

7、, *rc;（图 2-1-2）其中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倍多，所以需要开

8、3倍大小的数组void 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)对应不同的题目，我们会在线段树节点中添加另外的数据域，并随着线段的插 入或删除进行

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

10、点，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-2-2)要注

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

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

13、m)(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);elsereturn del(l, seg_treenum.mid, 2

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

15、信息，即从根节点 开始搜索整棵线段树，如果当前节点所代表的线段已被覆盖，则将统计长度加上当 前线段长度。否则，递归进入当前节点的左右子节点进行统计。实现代码图2-2-4 所示：int cal(int num)(if (seg_treenum.f)return seg_treenum.right eg_treenum.left + 1;if (seg_treenum.left + 1 = seg_treenum.right)当遍历到叶节点时返回return 0;return cal(2 * num) + cal(2 * num + 1);(图 2-2-4)小结：线段树作为一种数据结构只是解决问题

16、的一个工具，具体的使用方法则 非常灵活。以上介绍的仅仅为线段树的基础，在实际应用中，需要针对待解的题目 设计节点存储信息，以及修改维护操作等等。下面将由浅及深的介绍线段树的一些 应用，其中的一些线段树使用方法值得思考和借鉴。线段树的应用举例3.1染色问题问题链接： HYPERLINK /onlinejudge/showProblem.do?problemCode=1610 /onlinejudge/showProblem.do?problemCode=1610代码链接： HYPERLINK http:/www.acmdiy.nct/code/u/XadillaX/ZJU/16104 http:

17、/www.acmdiy.nct/code/u/XadillaX/ZJU/1610 ACMDIY平台为作者自主开发的一个在线代码库平台。问题大意:输入n个有色线段a,b，问最后每种颜色有多少连续段？(所有数字在0,8000 范围内)解题思路：这里是一个结构体：struct tree(int l, r, col, mid;tree *lc, *rc;l、r各代表左右端点，mid代表中点，col代表颜色。lc和rc各代表左 儿子和右儿子。1.创建线段树取最小和最大的两个数作为端点，建立线段树。当前节点的两个端点值之差等于一时，此时该节点即位叶子节点，不 用再向下分。否则，分裂该节点为a，(a + b

18、) / 2, (a + b) / 2, b;创建线段树时，注意初始化操作。2.线段树着色(根据不同的题目此操作各不相同，对zju_1610做分析)当前节点的颜色与将要涂的颜色color相同，直接return o当前线段树节点的两个端点和要涂的两个端点正好都相同，则将该节 点着为color，然后return。要涂的两个端点在当前节点的两个端点之间时：先将当前节点的颜色 向其子节点扩展，然后：要涂的右端点小于或等于当前节点middle = (a + b) / 2时，向左子 节点移动。要涂的左端点大于或等于当前节点middle = (a + b) / 2时，向右子 节点移动。else (1，2)向左

19、右子节点移动。源代码：/*File: p1610.cppAuthor: xadillax*Created on May 4, 2010, 7:20 PM*/#include #include #include #include #define NOCOL -1#define MULCOL -2using namespace std;struct tree(int l, r, col, mid;tree *lc, *rc;；tree *root;int n, l, r, col, i;int color8001, cnt8001;tree *init(int l, int r) 建立一棵线段树t

20、ree *rst;rst = (tree *)malloc(sizeof(tree);rst-l = l, rst-r = r, rst-mid = (l + r) / 2, rst-col = 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);return rst;void put(tree *p, int l, int r, int col)if(p-l = l & p-r = r)p-col = col;return;

21、if(p-col != MULCOL)p-lc-col = p-col;p-rc-col = p-col;p-col = MULCOL;if(l mid & r p-mid)put(p-lc, l, p-mid, col);put(p-rc, p-mid, r, col);elseif(p-mid rc, l, r, col);else put(p-lc, l, r, col);void cal(tree *p, int *color)int i;if(p-col = MULCOL)cal(p-lc, color);cal(p-rc, color);elseif(p-col != NOCOL)

22、for(i = p-l; i r; i+) colori = p-col;elsefor(i = p-l; i r; i+) colori = NOCOL;free(p);int main()while(scanf(%d, &n) != EOF)root = init(0, 8000);memset(color, 0, sizeof(color);memset(cnt, 0, sizeof(cnt);while(n-)scanf(%d%d%d, &l, &r, &col);put(root, l, r, col);cal(root, color);if(color0 != NOCOL) cnt

23、color0+;for(i = 1; i = 7999; i+)if(colori != NOCOL & colori != colori - 1)cntcolori+;for(i = 0; i 0) printf(%d %dn, i, cnti);printf(n);return 0;3.2城市景观问题链接：/JudgeOnline/problem?id=3277问题大意：如图所示，在一条水平线上有N个建筑物，建筑物都是长方形的，且可以 互相遮盖。给出每个建筑物的左右坐标值Ai,Bi以及每个建筑物的高度Hi， 需要计算出这些建筑物总共覆盖的面积。题目数据范围：建筑物个数 N： 1 = N =

24、 40000建筑物左右坐标值Ai, Bi： 1 = Ai,Bi = 109建筑物的高度Hi： 1 = Hi = 109解题思路：因为区间最大到10的9次方，开这么大的空间内存肯定不够，所以要离散 化，用map存入然后用iterator遍历得到的有序序列存入vector0然后以vector 的下标建立线段树，统计时若结点不是叶子结点，则它的值为左右孩子的值 之和，否则返回底*高。源代码：5#include #include #include using namespace std;typedef struct nodint left,right,mid;long long h;bool cove

25、r;node,*nd;typedef struct plong long start,end,hi;point;/元素个数上限和存储数组const int MAX_NUM=200000;第一次交 re,干脆开个大的node seg_tree3*MAX_NUM+1;point list40005;5此源代码来自文献参考中的第七项。 map my_map;map:iterator it;vector vec;/创建,l为左端点，r为右端点，num为在数组中的编号void make(int l,int r,int num)seg_treenum.left=l;seg_treenum.right=r;

26、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 & seg_treenum.right=r )if(seg_treenum.hhi) seg_treenum.h=hi;return ;if( r=seg_treenum.mid )Insert(l,r

27、,2*num+1,hi);elseInsert(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_treenum.right )return seg_treenum.h*( vec seg_treenum.right - vec seg_treenum.left );return cal( seg_treen

28、um.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开始有效for( it=my_map.begin(); it!=my_map.end();+it ) it-second=t+;vec.push_back( it-first );一vec.push_back

29、( 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;线段树的应用总结线段树是一种高效的数据结构。它的思想就是分治，非常基本也非常强大。在学习线段 树的过程中，要时刻记住，线段树只是一种解题的工具，学习线段树只是学习一种解题的思 维，就像图论中的BFS6 一样。至于在具体的题目中如何去

30、运用这个工具，则灵活的去建 树并维护相关信息。这也需要在平时进行积累，做题时才能应用熟练。线段树的练习题目推荐以下题目是各oj上比较有名的线段树题目Whu OnlineJudge HYPERLINK /oak /oak题目号：1071 1224 1361 1344Pku OnlineJudge HYPERLINK /JudgeOnline /JudgeOnline题目号 3225 2482 1177 1029 2182 2750 2104 2528 2828 2777 2886 2761Zju OnlineJudge HYPERLINK 题目号 2301 1128 1659 2112参考文献岳

31、云涛.浅谈线段数在信息学竞赛中的应用J.林涛.线段数的应用J,2004.刘汝佳，黄亮.算法艺术与信息学竞赛M.北京：清华大学出版社，2004.Thomas H.Cormen, Charles E.Leiserson, Ronald L.Rivest et al. Introduction to AlgorithmsM. 2nd Edition. America: The MIT Press, 2001.廖劲宇.pku 3277 （线段树+离散化）OL. HYPERLINK /liaojinyu282/archive/2010/01/16/5200521.aspx /liaojinyu282/archive/2010/01/16/5200521.aspx, 2010.朱凯迪.ZOJ1610 Count the ColorsOL.