注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

z55250825

一只蒟蒻

 
 
 

日志

 
 

【数据结构】【划分树】  

2013-12-25 21:50:54|  分类: 数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
    主要是边写边摸索下划分树到底该怎么写......为了能写出来首先咱们得叙述一下它的工作原理咩~
    划分树其实就是以线段树作为原型来构造的。划分树的基本思想就是对于要查找的第K大值的区间【s,t】我们拥有一个初始的区间【st,ed】,先将【st,ed】均匀划分成两个区间,第一个区间的数的最大值不大于第二个区间的数的最小值,并通过判断第二个区间里的在【s,t】里面的数的个数是否大于K来判断这个第K大值在左区间还是右区间,个数大于K则在第二个区间,否则在第一个区间,然后再递归区间查找即可。复杂度由于每一次都是均分的,所以为O(logN)。而每一个均分区间的信息都可以预处理得到,而存下这些预处理信息的便是划分树这样一个数据结构。
    首先是预处理均分区间的信息。咱们先需要一个二维数组存每一个区间,由于最多只有O(logN)层,所以开的数组可以为:
    (用的名字是partition(划分))
    var
    par,sum:array[0..maxn,0..20]of longint;(一般数据范围在2^20内,即10^6内)
   读入的数据第0层即为初始的。然后我们得划分区间,根据区间的定义实际上就是要咱们找中位数,这里我们就可以先用另一个数组a[]存 par[i][0],然后我们对那个数组排序,那么对于我们划分的区间【l,r】的区间,其中位数就是a[mid=(l+r)shr 1].
   至于为什么正确...可以归纳证明。首先对于区间【1,n】,mid显然为中位数成立。接下来假设对于区间【s,t】成立,那么我们把区间【s,t】划分成【s,mid-1】【mid,t】,那么前一个区间的必然都小于a[mid],后面的都不小于a[mid],则由划分树的定义易知前一个区间就对应a【s,mid-1】,所以其中位数就为midd=(s+mid-1)shr 1。证毕。
   那么我们找到了中位数,我们对于划分树中深度为dep的【l,r】,它可以划分为深度为dep+1的【l,mid-1】【mid,r】。首先for i:=l to r do,对于每一个数判断它是否不大于a[mid],如果不大于则划分到右边,即【dep+1】【mid,r】内,否则划分到【dep+1】【l,mid-1】内。然后再递归处理深度为dep+1的每一个区间。
 procedure partition(l,r,dep:longint);//新建区间x,其初始范围为【dep】【l,r】,要在它的基础上新建区间
                                                                            【dep+1】【l,mid-1】和【dep+1】【mid,r】
var i,ll,rr,mid:longint;
begin
    if l=r then exit;(如果划分到只剩下一个了则退出)
    mid:=(l+r+1)shr 1;
    ll:=l-1;rr:=mid-1;
    for i:=l to r do
        if (par[dep][i]>=a[mid])and(rr<r) then 
            begin
                 inc(rr);
                 par[dep+1][rr]:=par[dep][i];
                 {if i=l then sum[dep][i]:=0
                           else sum[dep][i]:=sum[dep][i-1]
             end}
        else 
            begin
                 inc(ll);
                 par[dep+1][ll]:=par[dep][i];
                 {if i=l then sum[dep][i]:=1
                           else sum[dep][i]:=sum[dep][i-1];}
             end;
     partition(l,mid-1,dep+1);
     partition(mid,r,dep+1);
end;
   顺便的,在划分的过程中,我们再维护一个sum域,sum【dep,i】表示深度为dep的被包含在区间【l,r】的数par【dep】【i】到其之前的par【dep】【l】间,共有多少数被划分到左区间。这一个东西是日后查找的关键。这个在上面程序的{}处。
   然后就是查找了。咱们的过程包含以下六个参数st,ed,dep,s,t,k,其含义为在划分树的区间【dep】【st,ed】中找划分树中【s,t】的第K大值。
function find(st,ed,s,t,k:longint):longint;
var i:longint;
 关键在于如何查找。这就需要我们之前用到的sum【】数组。对于区间【st,ed】显然对于被划分到同一个区间的,它们必然是相邻的。所以我们递归下去查找时要找的也是连续的区间。我们知道,sum【dep】【st-1】表示【s,st-1】中进入左区间的数的个数,sum【dep】【ed】表示的就是【s,ed】进入左区间的个数。那么【st,ed】中进入左区间的就是sum【dep】【ed】-sum【dep】【st-1】,如果个数<ed-st+1-k,那么第K大值就在右区间,否则在左区间。那么就这样递归下去即可。
  评论这张
 
阅读(69)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018