主席树学习笔记

今天学习了一个特殊的线段树结构，主席树。

概念：

主席树是一种可持久化的线段树结构，然后没了= =

用途：

主席树的最基本用途是查询a[l]$a[l]$……a[r]$a[r]$的x∈[L,R]$x/in /left [ L, R /right ]$的x$x$的个数。 引申还可以查询区间中第K小的数是什么。等等……

结构：

对于主席树的结构理解，我自己阅读多篇他人的博客，才终于明白了是怎么一回事。不知是博客写的不好还是我的理解能力太差= =大概是后者吧。 那我就按照自己的理解来讲清楚这究竟是什么样的结构。

初步结构要点：

初步结构分析：

进阶分析I：

鉴于a[i]的大小可能会非常大（eg. a[i] <= 109$10^9$）， 我们可以先将原序列离散化成N个数据点，再将N个数据点做成线段树。这样线段树的空间为O(N)$O(N)$， 因此主席树的空间为O(N2)$O(N^2)$。

进阶分析II：

分析T[i]与T[i + 1]。它们实际相差的范围只是后者比前者在数据范围中多了一个a[i + 1]。 分析T[i]到T[i + 1]的动态变化，其实只是从线段树的根节点到某个叶子节点这么一条路径发生了变化（保存的值都加了一）。于是利用指针，T[i + 1]的大部分节点都可以沿用T[i]，只是少量节点需要重新开辟（变化的节点）。 可以想象，这样就把一棵棵独立的线段树联系成了一个整体 -> 主席树。至于主席树究竟长成什么样，有点复杂，但是有一点是可以明确的，两棵相邻的线段树关系是非常清楚的。 由于大量地沿用了之前地节点，主席树的空间复杂度大大降低变成O(NlogN)$O(NlogN)$，变成了可以承受的范围了。

总结：

至此，一棵主席树就搭建完成了。关于时间复杂度，其实也就是两次线段树的复杂度，因此时间复杂度是O(NlogN)$O(NlogN)$

代码：