我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:2019年香港六彩全年资料 > 区间查询 >

求最朴素的线段树插入查询删除。pascal语言要比较优的。

归档日期:08-04       文本归类:区间查询      文章编辑:爱尚语录

  可选中1个或多个下面的关键词,搜索相关资料。也可直接点“搜索资料”搜索整个问题。

  在信息学竞赛中,经常遇到一些与区间操作有关的题目。比如统计若干个矩形的并集.计算若干区间线段的极值及总和等,这时就会用到“线段树”这种特殊的数据结构。

  线段树是一棵二叉树,记为T(a,b).参数a,b表示区间[a,b],其中b-a称为区间的长度,记为L。线段树T(a,b)也可递归定义为:

  处理的对象是线段或区间,目的是把一个区间[1..n]划分为一些[i,i+1]的单元区域,每个单元区域对应线段树中的一个叶子结点,每个结点用一个变量来记录覆盖该结点的线段条数。使用线段树要求知道所描述的区间端点可能取到的值。换句线..n]是从小到大排列的区同端点集合,对于任意一个待描述的闭区间P=[x,y].存在l≤i≤j≤n使得x=a[i]且y=a[j],这里i,j称为x,y的编号。注意:即使是实数坐标,在线段树中也只有整数含义。所以如无特殊说明,区间[x,y]中的x、y均是整数.即原始区间顶点坐标的编号。

  线段树有一些重要的特征.一是线段树是一棵平衡树.它的深度不超过log2L;二是线段树把区问上的任意一条线L条线段。所以线L)的时间内完成一条线段的插入,删除,查找等工作。下面结合一个题目给出线段树的常用操作过程。

  某次列车途经c个城市.城市蝙号依次为1到c,列车上共有s个座位.铁路局规定售出的车票只能是坐票.即车上所有的旅客都有座。售票系统是由计算机执行的.每一个售票申请包含三个参数.分别用O、D,N表示,o为起始站,D为目的地站.N为车票张数。售票系统对该售票申请作出受理或不受理的决定.只有在从O到D的区段内列车上都有N个点N个以上的空座位时该售票申请才被受理。请你写一个程序,实现这个自动售票乐统。

  输入文件为:第一行包含三个用空格隔开的整数c、s和R.其中l≤c≤60000,1≤s≤60000,1≤R≤60000。c为城市个数,s为列车上的座位数,R为所有售票申请总数。接下来的R行每行为一个售票申请.用三个由空格隔开的整数O,D和N表示,O为起始站.D为目的地站.N为车票站数,其中l≤D≤c,l≤O≤c.所有的售票申请按申请的时间从早到晚给出。

  输出文件为:RAlLWAY.OUT,共有R行,每行输出一个“YES”或“NO”.表示当前的售票申请被受理或不被受理。

  本题是一道在线的统计和查找题—区间的插入和查找。这类题目在规模比较小的情况是很容易做的,只需要简单模拟就可以了。但是,本题的规模是60,000.简单摸拟的复杂度是O(n2)的。60,000 x 60,000=3,600,000,000的运算量是无法承受的。所以,我们必须使用特殊的数据结构和算法来降低时间复杂度。

  区间的插入和查找让我们很容易联想到一类数据结构线段(区间)树。在线段树中插入和查找一个区间的时间复杂度都是O(log2n)的。只是本题比较特殊,要查找的是一段区间内的最大值,所以必须设计一个拥有查找区间最大值功能的线段树。

  首先.作为一棵线段树.树上的每个结点记录区间被覆盖的次数是必不可少的。此外.本题要查找区间内最大值,所以,还须记录每个区间内的最大值。这两个值是必须要记录的.而除去这两个值以外.也看不出还需要记录别的什么信息了。我们不妨就先令线段树只记录这两个值,看它们是否可维护。

  维护操作是关键。一个记录的值对于线段树是可维护的,是指插入和查找过程中.对它的维护复杂度在log2n级别以内。区间被覆盖次数的可维护性是显然的.这是每棵线段树都需要并且能够维护的值。

  我们再来看区间最大值的维护。实际上,如果要让每个结点都记录自己所表示的区间中的最大值,是不可能的。想像一下,如果插入一个能覆盖线段树根结点的线段.那么可能会改变整棵树上所有结点的最大值。所以.我们必须改变一下思路。

  我们知道,线段树查找的复杂度是O(log2n)的,查找的过程中可能会经历4log2n个区间.但是它最多覆盖2log2n个区间。前面的讨论已经让我们看到.光靠线n个区间的信息,是不足以帮助我们查找区间最大值的.所以我们必须利用另外的2log2n个区间。2log2n个未被覆盖的区间是一些相对“较大”的区间,它们是从根结点到覆盖结点之间的中间结点(内点),也就是说.从2log2n个覆盖结点到根结点的路径上必然会经过2log2n个未被覆盖的结点。此外,线段树中,父结点总是覆盖子结点(子结点是父结点分裂得到的)。如果有一个线段覆盖父结点的话,它必然也覆盖子结点。因此,有些信息,不妨放在父结点中.因为它的子结点涉及这些信息时,往回走经过父结点时,还可以补充进来。那么.什么信息是可以放在父结点上的呢?一定是涉及以它为根的子树上的所有结点的信息.例如这个区间的覆盖次数。这样,每个结点需要记录的只是它所表示的区间内的线段覆盖情况(这些线段包含在区间内)。

  我们重新定义一下结点上保存的最大值:“最大值”是指,由结点所表示的区间内的线段覆盖得到的区间覆盏最大值。这样的“最大值”是很容易维护的,设node为线段树上的一个结点.那么node上的最大值max有如下计算公式:

  至此.线段树的结构和维护方法已经设计完毕.为了理清思路.我们再来总结一遍:

  有了以上的线段树模型.我们只需要在线段树上作一个简单的模拟即可解决本题。算法的时间复杂度是O(qlog2n)的.其中q表示插入和查找的次数,n表示结点个数。

  本题除了线段树的安现方法外,还可以用分割区间来做(将长度为n的区间分割成n1/2个长度为n1/2的区间).这种方法每次插入和查找的时问复杂度都是n1/2的.q次操作就是O(qn1/2).分割区间在速度上比线段树慢一些,但是代码更容易实现.而且对于60000的规模,O(qn1/2)完全可以承受.

本文链接:http://mpragency.com/qujianchaxun/665.html