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

一个蒟蒻的代码回收站

最后一次省选求rp

 
 
 

日志

 
 

主席树专题  

2014-04-18 11:06:00|  分类: 算法 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

关于主席树什么的东西已经烂大街了吧……随便百度一下就能找到一堆……可是我太弱,看了好半天才看懂,于是发些自己的理解攒攒人品(其实主要是为了自己以后忘记的时候可以拿来看看)

首先仰慕一下主席树的发明人:@fotile96 主席!


主席树是一棵(啊呸,是很多棵)权值线段树。

正常情况下,权值都是2^31范围内的,如果全部建出来的话太恐怖,但是用到的数没有几个,所以我们先离散化,把要用的数预处理出来,这样就可以建树了。


我们先考虑没有修改的版本

利用前缀和思想,把每个前缀都保存权值线段树(暴力建树不管时间还是空间都会跪的,建树方法后面再讲)。

由于保存的是权值线段树,权值线段树是可以加减的(当然普通线段树也可以加减,可是加减出来会是奇怪的东西= =)

对于一段区间[l,r],我们只要把r的线段树减去l-1的线段树就可以了(当然你也不能暴力去加减线段树树,不然复杂度是O(n)的,正确的加减树的方法是,先加减根节点,然后判断k是在左子树还是右子树,然后进行递归,这样是O(logn)的)


开始填坑:这样建树的时间空间复杂度都是O(n^2)级别的,显然是要跪的。我们发现,后面的线段树比前面的线段树只不过是加了一个数字。在线段树里加一个数字我们都知道是logn的对吧,所以我们只要对从根到那个节点的这条链重新建过就好了,其他的不用变,直接把指针指向原来的子树即可。

这就是传说中的——可持久化,主席树就是一棵可持久化线段树


时间复杂度:预处理O(nlogn)+每次询问O(logn)。

至于空间嘛……主席树是一种非常烧内存的数据结构= =……不过现在一般都是128M的空间了,应该不会有出题人sxbk的卡空间


现在考虑修改版本。

由于有修改,我们不能用前缀和了,不然一次修改就要修改一堆树。

由于主席树可加可减的良好性质,我们可以用树状数组套上这个主席树。

注:这里的主席树跟上面的主席树不是同一种东西,由于树状数组保存的东西重叠部分计算比较麻烦,这里的主席树没有可持久化了。

所以,树状数组套上去的其实就是一棵普通的权值线段树。

于是,前面的问题又出现了,如何不MLE?

我们发现,树状数组保存的东西是很少的(位置x只保存向前数lowbit(x)个数),所以这里的主席树大多的空间都是无用的。于是,我们对于数量为0的东西,只用一个空节点表示,等要用的时候再建出来。

于是,修改的时候,我们像树状数组和线段树一样修改。

查询的时候呢,我们要把一大堆的主席树加减(主席树加减的正确姿势?上面有啦)

然后就差不多了。

时间复杂度:预处理O(nlog^2 n)+每次询问O(log^2 n)

只是……这样更烧内存了= =


练习题:

poj 2104 不支持修改的区间k大

bzoj 1901(zju 2112)支持单点修改的区间k大。

bzoj 3110 支持区间修改的区间k大。

参考资料

seter的blog

陈立杰《可持久化数据结构研究》

  评论这张
 
阅读(5)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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