柒葉灬 的博客

柒葉灬 的博客

主席树进阶(个人笔记13)

posted on 2018-12-05 16:43:58 | under 个人笔记 |

主席树专题后总结


基础

主席树就是很多棵线段树,通过每两棵线段树差别不大来节省空间。

最基础的题:区间求第K大值(没有修改)。 $O(nlogn)$


进阶

稍微难一点就是:带修主席树。

我们知道,基础的主席树是一个前缀和,那么,我们希望单调修改后,后面的前缀和也一起更改,想到树状数组套主席树

这也算是树套树入门的题目:区间求第K大值(带修改) $O(nlog^2n)$


活用

题目不可能给你像区间K大值这样的裸题,所以我们要明白什么样的题目可以用主席树。

主席树核心的思想就是可持久化

所以遇到那种修改之后还询问之前的,那么就可以考虑能否用主席树了。

或者是遇到希望开很多棵线段树的,就可以考虑主席树了。


技巧

主席树重点是明白根是什么,存下标还是存数值,有些题目弄懂这些就解决了。

还有节点开多大也很重要,开小了会RE,大了不测会MLE,不要以为主席树省的空间可以无限使用。(用主席树一定要测空间

主席树根如果是下标的话,在不能保证空间的情况下不要开1-1e9的范围,最好把数值离散化后再算。

一定要注意左端点是0还是1,有时候求区间可能会开到0