前置知识：线段树

基本原理

主席树，又名可持久化权值线段树，是一种可持久化线段树。当然，很多地方通常也会用主席树来指代可持化线段树。它是最常见的可持久化数据结构之一。

要想实现线段树的可持久化，有一个很笨的方法：每次更改都复制一份进行修改。很显然，这在时空上效率都极其低下。我们要考虑如何节省时间和空间。此时我们很容易想到：只记录修改的节点。由于线段树的深度是的，所以每次单点修改最多修改的节点，因此也可以在的空间内实现历史记录。