主席树进阶（个人笔记13）

## 主席树专题后总结 ------ #### 基础 主席树就是很多棵线段树，通过每两棵线段树差别不大来节省空间。 最基础的题：区间求第K大值（没有修改）。$O(nlogn)$ ------ #### 进阶 稍微难一点就是：带修主席树。 我们知道，基础的主席树是一个前缀和，那么，我们希望单调修改后，后面的前缀和也一起更改，想到**树状数组套主席树**。 这也算是树套树入门的题目：区间求第K大值（带修改）$O(nlog^2n)$ ------- #### 活用 题目不可能给你像区间K大值这样的裸题，所以我们要明白什么样的题目可以用主席树。 主席树核心的思想就是**可持久化**。 所以遇到那种**修改之后还询问之前的**，那么就可以考虑能否用主席树了。 或者是遇到希望**开很多棵线段树**的，就可以考虑主席树了。 ------- #### 技巧 主席树重点是明白根是什么，**存下标还是存数值**，有些题目弄懂这些就解决了。 还有节点开多大也很重要，开小了会RE，大了不测会MLE，不要以为主席树省的空间可以无限使用。（**用主席树一定要测空间**） 主席树根如果是下标的话，在不能保证空间的情况下不要开1-1e9的范围，最好把数值离散化后再算。 一定要注意左端点是0还是1，有时候求区间可能会开到0 -------