线段树及其应用

线段树及其应用

ID:40225787

大小:193.50 KB

页数:25页

时间:2019-07-27

线段树及其应用_第1页
线段树及其应用_第2页
线段树及其应用_第3页
线段树及其应用_第4页
线段树及其应用_第5页
资源描述:

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

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

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。