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

vfleaking的博客

My name is VFlea King

 
 
 

日志

 
 

3065: 带插入区间K小值 系列题解之三——划分树崛起  

2013-02-27 09:28:18|  分类: 衡阳八中 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
本篇日志介绍第三种解法:(如果不喜欢这种解法,没关系!可以看后面的日志!)
拓展版划分树

嘛……这种做法……要知道拓展版划分树,先要知道划分树。由于主席树横空出世,划分树已然成为了时代的默泪,可能大家有点忘了吧。

我们先来看不带插入应该怎么用划分树做。
划分树每次选中位数,然后把区间劈开。在带修改的情况下,这已经不适用了。
我们意识到:何必用中位数划分呢?用权值划分不就行了?
于是可以开一棵线段树,维护的是权值范围。每个结点上都是一棵平衡树,平衡树代表的序列是按原数组顺序存储权值在线段树结点权值范围内的所有元素。由于一个元素位置是确定的,那么在平衡树中就很好比较谁先谁后了。
查询就是类似划分树的查询,在每个线段树结点那里决定到底是去左子树还是右子树,最后走到叶子就是答案。
修改就是沿途从线段树结点里的平衡树里删除元素,再沿途从线段树结点里的平衡树里插入元素。
自行YY下吧囧囧囧,应该还是很好理解的。

好……现在插入来了。
何有于我哉?
重要变化无非就是不能确定元素位置了,在平衡树中没法比较谁先谁后。
没关系嘛……插入元素的时候并不影响其他元素的相对位置关系。
在线段树的最上层的[0, m]这个区间里的平衡树里有所有元素。(m是权值最大值)
那么就爽了嘛。要比较两个元素谁先谁后,就在最上层的那个平衡树里取它们两个各自的在原序列中的位置,就行咯。
update:
是albus YY出来的方法……之前问他的解法的过程中好像有点误会……上面这行话一定误导了很多小朋友……
谜之声:你要不要这么不靠谱……自己没仔细算时间复杂度就把题解贴出来了……乃又调皮了……
实际插入的过程中,不必每次比较两个元素时都在最上层的平衡树里搞。
那不比较,肿么插入呢!
办法还是有的,如果知道我们要插入的结点到底是在平衡树中排名第几还是可以插入的嘛~在平衡树中多加一个size域记录子树的大小就行鸟~
于是我们在插入之前就动态维护下它到底排名第几。
好,那么在最上层的平衡树中,我们是可以容易地求出要插入的结点是在平衡树中排名第几的,此时也就是它插入后在题目要你维护的那个序列中的位置,也就是输入数据……
那么现在考虑我们已经在线段树中某个结点上处理了许多事情,现在要继续向下走插入了。
那么我们现在知道在这个结点的平衡树 中排名第几,想要知道走到它的孩子之后,在孩子的平衡树 T 中排名第几。
考虑原版划分树是怎么处理的?前缀和cntLeft记录划分到左边的数的个数。
所以就清楚了~现在我们已经在当前结点的平衡树 中插入完毕了,我们求出排名在我插入的那个结点前面,划分到左子树的数的个数,就能和原版划分树一样处理了~若没懂具体细节及公式可以复习下原版划分树~
所以平衡树的每个结点再记录一个值isLeft,标记它是不是被划分到左子树去了。
所以平衡树的每个结点再记录一个值cntLeft,记录子树中被划分到左子树的结点的个数。
于是这棵平衡树带了N多标记……
这下应该不会有错误了……orz SillyHook 提醒了我……

查询还是查询。
插入还是插入。
修改就是删了再插入。

三个操作的时间复杂度都是O(logmlogn)

这种做法不用开函数式,空间占用得很少。
之前两篇日志都是主席式数据结构,是在原有的主席树模式上的拓展。
而这篇日志介绍的是正统划分树的后裔,代码比前两个好写。
划分树崛起的时代来临了?

其实我觉得我刚才说的拓展版划分树完全没有讲清楚?
不过我觉得理解了划分树的话上面的想法就能呼之欲出了~

感谢albus提供代码实现。
这里的平衡树的话……写splay在BZOJ上光荣TLE。
写treap就能过了。
就当splay常数巨大的一个证明警醒世人了。
  评论这张
 
阅读(2915)| 评论(1)
推荐 转载

历史上的今天

评论

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

页脚

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