RainAir
My OI Blog
RainAir
主席树学习笔记

在学习主席树之前一定要先学会线段树

主席树定义

主要思想:主席树是利用函数式的编程思想使得线段树支持查询历史版本,同时充分的利用不同版本之间的共同版本来减少时间和空间复杂度的数据结构。一棵线段树的节点维护的是当前节点所对应的区间信息,若每次区间不同则处理较为困难。

它最基本的运用是区间第 $ k $ 小问题。

权值线段树

传统的线段树用于维护区间,可以方便的查询区间信息,权值线段树是每个叶子结点存储了某个元素出现的次数,一条线段的总和表示区间内所有数出现次数的总和。

利用权值线段树可以求出整体第 $ k $ 小。

具体方法:先离散化一遍,从根节点开始寻找,设当前左子树大小为 $ ls $ ,如果 $ k \leq ls$ ,那么说明该区间第 $ k $ 大是左子树中的第 $ k $ 小;反正,该区间第k大是右子树所代表的区间第 $ k-ls $ 小。

时间复杂度为$ O(log_2 N) $

静态主席树

我们接下来处理对于给定的不同区间的询问,查询该区间第 $ K $ 小。

我们先转化问题:如果我们有办法快速求整个区间的最值,那么我们如何回答区间 $ [l,r] $ 的最值询问呢?

最显然易见的方法是前缀和。

发明者的原话:

对于原序列的每一个前缀[1···i]建立出一棵线段树维护值域上每个数出现的次数,则其树是可减的。

那么,我们对于每一个前缀来维护一个上文提到的「权值线段树」即可。

我们在查询区间 $ [l,r] $ 的第 $ K $ 小时,转化为求 $ [1,r] $ 中去除 $ [1,l-1] $ 的元素后的第 $ K $ 大。

因为这种建树方式建出来的树是可减的,我们在递归过程中减去 $ [1,l-1] $ 的部分即可。

但是如果对于每一个前缀都建立一棵线段树,无论是时间还是空间是不可承受的,甚至不如排序处理快。

如何优化?

我们可以发现,其实我们在建树的时候,初始化静态区间的值相当于重新构建一个线段树。重新构建的线段树与之前的线段树相比,只是更改了最多 $ log_2N $ 个点。那么我们每次插入一个新的数时,我们只需要更改那 $ log_2N $ 个结点即可。

这样我们每次新插入一个点的时间复杂度从 $ Nlog_2N $ 暴力建树优化到了 $ log_2N $ 。

空间复杂度也明显优化了。

多提一点:我目前写过的主席树都是用指针写的,一般都写内存池,因为 new 开点会 TLE

题目&代码

题目链接

例题一:给定一个区间,维护一个操作

  • 询问区间 $ [l,r] $ 的第 $ K $ 小元素。

代码:

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/98
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

主席树学习笔记
在学习主席树之前一定要先学会线段树 主席树定义 主要思想:主席树是利用函数式的编程思想使得线段树支持查询历史版本,同时充分的利用不同版本之间的共同版本来减少时间和空间复杂度的…
扫描二维码继续阅读
2018-07-20
标签
近期评论