线段树及其应用

《线段树及其应用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、线段树及其应用引例数列操作假设有一列数{Ai}(1≤i≤n)，支持如下两种操作：将Ak的值加D。（k,D是输入的数）输出As+As+1+…+At。（s,t都是输入的数，S≤T）输入：第一行一个整数n，第二行为n个整数，表示{Ai}的初始值。第三行为一个整数m，表示操作数下接m行，每行描述一个操作，有如下两种情况：ADDkd(表示将Ak加d，1<=k<=n，d为整数)SUMst（表示输出As+…+At）输出：对于每一个SUM提问，输出结果如果按题目要求直接模拟：每一个ADD操作的复杂度是O(1)每一个SUM操作的复杂度是O(N)可见对于M次SUM询问，复杂度是O(NM

2、)有没有更好的方法呢？这里我们提出一种称之为线段树的数据结构。引例数列操作引例线段树的定义线段树是一棵二叉树，记为T(a,b)，参数a,b表示区间[a,b]，其中b-a称为区间的长度，记为L。线段树T(a,b)也可递归定义为：若L>1:[a,(a+b)div2]为T的左儿子；[(a+b)div2,b]为T的右儿子。若L=1:T为叶子节点。表示区间[1,10]的线段树样例：[1,10][1,5][5,10][1,3][3,5][5,7][7,10][1,2][2,3][3,4][4,5][5,6][6,7][7,8][8,10][8,9][9,10]引例线段树的建立我

3、们知道，对于长度为n的线段建立的线段树，至多只有nlogn个节点，故建立线段树的复杂度是O(nlogn)ProcedureMakeTree(a,b)VarNow:LongintBegintot←tot+1Now←totTree[Now].a←aTree[Now].b←bIfa+1

4、开始遍历线段树中每个包含了k的区间节点，然后修改S域。由于这样的区间至多只有logn个，所以一次ADD操作的复杂度是O(logn)引例SUM操作对于待计算的区间[s,t]：Functiongetsum(v):integer;if(s<=Tree[v].a)and(Tree[v].b<=t)thengetsum:=Tree[v].Selsebegintot:=0;if[s,t]和Tree[v].Left表示的区间相交thentot:=tot+getsum(Tree[v].Left);if[s,t]和Tree[v].Right表示的区间相交thentot:=tot+ge

5、tsum(Tree[v].Right);getsum:=totend;我们不难发现这个过程中所遍历到的区间数（节点数）和线段树的深度同阶，因此时间复杂度是O(logn)引例问题的解决综上，M次操作的时间复杂度为O(Mlogn)通过引入线段树的数据结构，虽然ADD操作的复杂度提高到了O(logn)。但SUM操作变得更快(O(logn))。从而也使得算法在大数据处理上更加高效。例一Picture(IOI98)墙上贴了一些矩形的张贴画和照片。他们的边都是垂直或者水平的。每个矩形可以部分后者全部被其他的矩形覆盖。把这些矩形看作一个整体，他们的边界长度就是他们的轮廓长度。所有

6、顶点坐标都是整数。任务：写一个程序计算轮廓长度。下面的图1是一个7个矩形的例子：图1：七个矩形这些矩形的轮廓如图2所示图2：图1中7个矩形的轮廓例一Picture(IOI98)预处理：如右图所示，用2n条横线与2n条纵线将坐标平面重新进行划分。定义新的坐标轴，并记录每一个“元线段”的长度。这样就只剩下了2n*2n个坐标点，便于今后的计算。离散化，将2n条矩形的横边和2n条纵边取出来，分别计算例一Picture(IOI98)做完预处理之后，如果直接计算，不难想到O(n2)的算法。事实上，利用线段树我们可以设计出一个时间复杂度为O(nlogn)的高效算法。在分析算法之前

7、，我们先来看看线段树上插入和删除线段的操作。例一线段树的插入、删除(1)增加一个Tree[i].Cover域，记录该区间（线段）被覆盖的次数。则在线段树中插入线段[c,d]的代码段如下：ProcedureInsert(v)BeginIf(cthenInsert(Tree[v].Right)End例一线段树的插入、删除(2)删除线段[c,d]的操作，只需要将Tree[v].C