什么是主席树

主席树这个名字看上去很高级，其实不然，它还有另一个名字——可持久化线段树。

什么是可持久化

可持久化顾名思义就是它可以变得持久，就是我们对他不断进行单点修改后，突然查询它的某一个历史版本，这就叫可持久化。

引入例题

洛谷3919:可持久化数组

题目大意

如题，你需要维护这样的一个长度为 \(N\ (1\le N\le 10^6)\) 的数组，支持如下几种操作

1.在某个历史版本上修改某一个位置上的值
2.访问某个历史版本上的某一位置的值

此外，每进行一次操作（对于操作 2，即为生成一个完全一样的版本，不作任何改动），就会生成一个新的版本。版本编号即为当前操作的编号（从 1 开始编号，版本 0 表示初始状态数组）

此时我们就需要用到主席树了。

分析

问题：这里我们为什么能直接用数组来做？
很简单，如何我们用数组来做的话每改变一个数，我们就要新建一个数组并将其他没有改变的也一起复制下来，而\(1\le N \le 10^6\) 空间不支持。~~（如果可以就没必要做了）~~

思考：问什么明明只修改了一个数，却必须将其他的数也复制一遍？
那是因为数组的一级索引所决定的。

什么是索引

索引是一种单独的、物理的对数据库表中一列或多列的值进行排序的一种存储结构，它是某个表中一列或若干列值的集合和相应的指向表中物理标识这些值的数据页的逻辑指针清单。
索引的作用相当于图书的目录，可以根据目录中的页码快速找到所需的内容。

最优索引

问题：怎样的索引是最高效呢？
这里，我们设索引大小为 \(k\),那么索引的层数为 \(\log_kn\),则每次修改的数量为 \(k\log_kn\)。
\(k\log_kn=\log_kn^k=k\dfrac{\ln n}{\ln k}=\ln n\dfrac{k}{\ln k}\)
设\(f(n)=\dfrac{k}{\ln k}\)
\(f'(n)=\dfrac{\ln k+1}{\ln^2 k}=\left(\dfrac{1}{\ln k}\right)^2+\dfrac{1}{\ln k}\)
在 \(1\le k\le n\) 的情况下，\(\ln k\in\left[0,\infty\right]\)。
所以 \(k_{\min}=e\ (\ln k=1)\)。
即索引为 \(k=2\) 或 \(k=3\) 时最优。
这里我们取 \(k=2\),因为它可以用线段树维护。