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

vfleaking的博客

My name is VFlea King

 
 
 

日志

 
 

3065: 带插入区间K小值 系列题解之二——Treap套函数式线段树  

2013-02-24 22:11:22|  分类: 衡阳八中 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
本篇日志介绍第二种解法:(如果不喜欢这种解法,没关系!可以看后面的日志!)
Treap套函数式线段树

这是hzhwcmhf知道了解法一后提出的。
Treap的插入众所周知是期望O(logn)的,可是一个惊人的事实是,插入后旋转的期望次数是2次。旋转次数竟然是期望O(1)的!
假设s是以这个结点为根的子树的大小,如果你旋转一次耗费时间是O(s)的,那么插入后旋转的耗时竟然是期望O(logn)的!
非常惊人的结论!
详细证明好像没有中文资料,可以参考:http://faculty.washington.edu/aragon/pubs/rst96.pdf

所以Treap套函数式线段树就可捉了。
用Treap维护原序列,每个结点上带一个线段树维护以它为根的子树中出现的权值。
旋转的时候:
     y                            x
    /  \                          /  \
  x    c     -------->      a    y
 /  \                                /  \
a   b                             b   c
注意到子树a、b、c的线段树标记是不会变的,而x的线段树可以直接用原先y的线段树,y的线段树就暴力合并b、c的。
如果写的是函数式线段树,那么在旋转上的耗时就是O(logn)的。沿途插入是需要O(log^2n)的。
当然也可以直接不写函数式就写线段树,这样旋转上的耗时就是O(log^2n)的。

这样就解决了插入。
至于修改和查询,可以参考前一篇题解的修改和查询的做法,是一样的。

update:有人求代码,我发一下好了。http://fayaa.com/code/view/27499/
这份代码是hzhwcmhf根据我之前的替罪羊树那个代码改的。
  评论这张
 
阅读(3096)| 评论(5)
推荐 转载

历史上的今天

评论

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

页脚

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