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

To be completed

我回来了

 
 
 

日志

 
 

归并树与划分树  

2010-08-16 23:24:40|  分类: ACM |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
据说最近挺热门的,想起寒假学过归并树,结果现在什么都不记得了,模拟了下归并排序终于想起来了
归并树
以1 5 2 6 3 7为例:
把归并排序递归过程记录下来即是一棵归并树:
        [1 2 3 5 6 7]
    [1 2 5]      [3 6 7]
   [1 5] [2]    [6 3] [7]
  [1][5]        [6][3]
用对应的下标区间建线段树:(这里下标区间对应的是原数列)
            [1 6]
     [1 3]      [4 6]
  [1 2] [3]   [4 5][6]
  [1][2]      [4][5]
每次查找[l r]区间的第k大数时,在[1 2 3 4 5 6 7]这个有序的序列中二分所要找的数x,然后对应到线段树中去找[l r]中比x小的数有几个,即x的rank。由于线段树中任意区间对应到归并树中是有序的,所以在线段树中的某个区间查找比x小的数的个数也可以用二分在对应的归并树中找。这样一次查询的时间复杂度是log(n)^2。
要注意的是,多个x有相同的rank时,应该取最大的一个。

划分树
同样以1 5 2 6 3 7为例:
根据中位数mid,将区间划分成左子树中的数小于等于mid,右子树中的数大于等于mid,得到这样一棵划分树:
        [1 5 2 6 3 7]
     [1 2 3]      [5 6 7]
   [1 2]  [3]    [5 6] [7]
  [1] [2]        [5] [6]
注意要保持下标的先后顺序不变
对每一个区间,用sum[i]记录区间的左端点left到i有几个进入了左子树,即有几个数小于等于mid
用对应的下标区间建线段树:(这里下标区间对应的是排序后的数列)
            [1 6]
     [1 3]      [4 6]
  [1 2] [3]   [4 5][6]
  [1][2]      [4][5]
每次查找[l r]区间的第k大数时,先查看当前区间[left right]下的sum[r] - sum[l - 1]是否小于等于k,如果是,则递归到左子树,并继续在[left + sum[l - 1], left + sum[r] - 1]中找第k大数;
否则,进入右子树,继续在[mid + l - left + 1 - sum[l - 1], mid + r - left + 1 - sum[r]]找第k - sum[r] + sum[l - 1]大数
这样一次查询只要logn的复杂度

对于建划分树的方法,我一开始是先建完一层,再往下递归,过了PKU2104后,交HDU2665WA,后来发现对于0 0 -1这样的数据,下一层本应该是-1 0 0,而我的程序还是0 0 -1,原因就是会有很多相同的元素等于mid。于是我就找什么是唯一的,很容易想到数组的下标,仔细观察,如果从划分树叶子回溯,相当于在对数组下标进行归并排序,于是我的问题就解决了~

思考:划分树可以求逆序数吗,划分树中如何求一个数在某个区间的rank
  评论这张
 
阅读(5652)| 评论(11)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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