下载

2下载券

加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 高二下期4月12日线段树

高二下期4月12日线段树.doc

高二下期4月12日线段树

faint
2018-09-07 0人阅读 举报 0 0 暂无简介

简介:本文档为《高二下期4月12日线段树doc》,可适用于工程科技领域

安阳一中信息学奥赛培训教材线段树一、线段树的定义在信息学竞赛中经常遇到一些与区间操作有关的题目。比如统计若干个矩形的并集.计算若干区间线段的极值及总和等这时就会用到“线段树”这种特殊的数据结构。线段树是一棵二叉树记为T(ab).参数a,b表示区间a,b其中ba称为区间的长度,记为L。线段树T(a,b)也可递归定义为:若L>:a,(ab)div为T的左儿子(ab)div,b为T的右儿子。若L=l:T为叶子结点。处理的对象是线段或区间目的是把一个区间n划分为一些i,i的单元区域每个单元区域对应线段树中的一个叶子结点每个结点用一个变量来记录覆盖该结点的线段条数。使用线段树要求知道所描述的区间端点可能取到的值。换句话说,设An是从小到大排列的区同端点集合对于任意一个待描述的闭区间P=xy.存在l≤i≤j≤n使得x=ai且y=aj,这里i,j称为x,y的编号。注意:即使是实数坐标在线段树中也只有整数含义。所以如无特殊说明区间x,y中的x、y均是整数.即原始区间顶点坐标的编号。一般情况下线段树的结点类型定义如下:typelinetree=^nodenode=recordi,j:integer{结点表示的区问的顶点标号i.j}count:integer{覆盖这一结点的区间数}lchild,rchild:linetree{二叉树的两个子结点}end图是一棵典型的线段树描述的区间端点可以有种取值。二、线段树的基本操作和应用线段树有一些重要的特征.一是线段树是一棵平衡树.它的深度不超过logL二是线段树把区问上的任意一条线段都分成不超过logL条线段。所以线段树能在O(logL)的时间内完成一条线段的插入删除查找等工作。下面结合一个题目给出线段树的常用操作过程。【例】售票系统【问题描述】某次列车途经c个城市.城市蝙号依次为到c列车上共有s个座位.铁路局规定售出的车票只能是坐票.即车上所有的旅客都有座。售票系统是由计算机执行的.每一个售票申请包含三个参数.分别用O、DN表示o为起始站D为目的地站.N为车票张数。售票系统对该售票申请作出受理或不受理的决定.只有在从O到D的区段内列车上都有N个点N个以上的空座位时该售票申请才被受理。请你写一个程序实现这个自动售票乐统。输入:输入文件为:RAILWAYIN,第一行包含三个用空格隔开的整数c、s和R.其中l≤c≤≤s≤≤R≤。c为城市个数s为列车上的座位数R为所有售票申请总数。接下来的R行每行为一个售票申请.用三个由空格隔开的整数OD和N表示O为起始站.D为目的地站.N为车票站数其中l≤D≤cl≤O≤c.所有的售票申请按申请的时间从早到晚给出。输出:输出文件为:RAlLWAYOUT,共有R行,每行输出一个“YES”或“NO”.表示当前的售票申请被受理或不被受理。【样例输入】RAIlWAYINlI【样例输出】RAILWAYOUTYESYESNONO【问题分析】本题是一道在线的统计和查找题区间的插入和查找。这类题目在规模比较小的情况是很容易做的只需要简单模拟就可以了。但是本题的规模是,.简单摸拟的复杂度是O(n)的。,x,=,,,的运算量是无法承受的。所以我们必须使用特殊的数据结构和算法来降低时间复杂度。区间的插入和查找让我们很容易联想到一类数据结构线段(区间)树。在线段树中插入和查找一个区间的时间复杂度都是O(logn)的。只是本题比较特殊要查找的是一段区间内的最大值所以必须设计一个拥有查找区间最大值功能的线段树。下面我们就来设计这样的一个线段树。首先.作为一棵线段树.树上的每个结点记录区间被覆盖的次数是必不可少的。此外.本题要查找区间内最大值所以还须记录每个区间内的最大值。这两个值是必须要记录的.而除去这两个值以外.也看不出还需要记录别的什么信息了。我们不妨就先令线段树只记录这两个值看它们是否可维护。维护操作是关键。一个记录的值对于线段树是可维护的是指插入和查找过程中.对它的维护复杂度在logn级别以内。区间被覆盖次数的可维护性是显然的.这是每棵线段树都需要并且能够维护的值。我们再来看区间最大值的维护。实际上如果要让每个结点都记录自己所表示的区间中的最大值是不可能的。想像一下如果插入一个能覆盖线段树根结点的线段.那么可能会改变整棵树上所有结点的最大值。所以.我们必须改变一下思路。我们知道线段树查找的复杂度是O(logn)的查找的过程中可能会经历logn个区间.但是它最多覆盖logn个区间。前面的讨论已经让我们看到.光靠线段覆盖的logn个区间的信息是不足以帮助我们查找区间最大值的.所以我们必须利用另外的logn个区间。logn个未被覆盖的区间是一些相对“较大”的区间它们是从根结点到覆盖结点之间的中间结点(内点)也就是说.从logn个覆盖结点到根结点的路径上必然会经过logn个未被覆盖的结点。此外线段树中父结点总是覆盖子结点(子结点是父结点分裂得到的)。如果有一个线段覆盖父结点的话它必然也覆盖子结点。因此有些信息不妨放在父结点中.因为它的子结点涉及这些信息时往回走经过父结点时还可以补充进来。那么.什么信息是可以放在父结点上的呢一定是涉及以它为根的子树上的所有结点的信息.例如这个区间的覆盖次数。这样每个结点需要记录的只是它所表示的区间内的线段覆盖情况(这些线段包含在区间内)。我们重新定义一下结点上保存的最大值:“最大值”是指由结点所表示的区间内的线段覆盖得到的区间覆盏最大值。这样的“最大值”是很容易维护的设node为线段树上的一个结点.那么node上的最大值max有如下计算公式:node->max=max{node>leftchild>max,node>rightchild>max}node>occur其中node>occur表示node所在区问被覆盖的次数。至此.线段树的结构和维护方法已经设计完毕.为了理清思路.我们再来总结一遍:.线段树记录的信息()结点所表示区间的左右边界:(eftbound和rightbound)()结点左右孩子的位置(leftchild和rightchild)<)结点被覆盖的次数:(occur)()结点内覆盖的最大值.(max).线段树的维护<)左右边界:node>leftchild>leftbound=node>leftboundnode>leftchild>righthound=(node>leftbouudnode>rightbound)node>rightchild>leftbound=(node>leftboundnode>rightbound)node>rightchild>rightbound=node>rightbound()结点被覆盖的次数:insert(,r,node)if(l<=node>leftbound&&r>=node>rightboundnode>occurelse{insert(,r,node>leftchild)insert(l,r,node>rightchild)}()结点内最大值:node>max=max{node>leftchild>max,node>rightchild>max}node>occur有了以上的线段树模型.我们只需要在线段树上作一个简单的模拟即可解决本题。算法的时间复杂度是O(qlogn)的.其中q表示插入和查找的次数n表示结点个数。本题除了线段树的安现方法外还可以用分割区间来做(将长度为n的区间分割成n个长度为n的区间).这种方法每次插入和查找的时问复杂度都是n的.q次操作就是O(qn).分割区间在速度上比线段树慢一些但是代码更容易实现.而且对于的规模O(qn)完全可以承受.【参考程序】第页共页

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/10

高二下期4月12日线段树

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利