之前也写过一篇讲主席树的文章，但是那时候理解的实在是太片面了。

        首先，所谓可持久化，就是说我有很多个操作，但是我在任意时刻可以回到之前的某一个操作之前的样子。或者说可以知道某一个操作之前的信息。对于普通的线段树来说，肯定是不能够支持的，那么我们如何解决这个问题呢？



        最简单的，我们考虑暴力一点的方式，对于每一个操作，我在之前的基础上单独建立一棵线段树，把之前的线段树保留，供我以后回到某一个操作之前使用。如此一来，对于m个操作，我们就要建立m个线段树，每个线段树空间位nlogn，那么空间复杂度就是O(MNlogN)，在时间上每次建树和操作也是NlogN级别，因此时间复杂度也是O(MNlogN)。对于数据结构题，一般来说10^5级别的数据范围来说显然是不能令人满意的。

        这样，我们才有了可持久化线段树（主席树）存在的必要。为了介绍这个，我们先想象一下一个普通的线段树的每一个操作是如何进行的。对于任意一个操作，我自然是从最上面的节点开始往下，一直到我要对应操作的位置/区间，那么修改的节点最多就有logN个。我们特别强调，这里修改的节点只有logN个。那么，我们是否可以利用这个对我们暴力建立m个线段树进行优化呢？答案是肯定的。考虑到每次改变的节点其实不多，我们对于每一个操作可以不建立新的线段树，而是与原本的线段树共用一些没有修改的点，对于改变的节点则做出更新。

       如此一来，我们每一个操作，只需要新建 logN 个节点，对应也修改这么多节点。因此每一个操作在时间和空间上的复杂度都是O(logN)。总的来说复杂度就是O(NlogN+MlogN)，其中前一个NlogN表示建树的时候的代价。

     下面就具体讲讲每一个操作如何执行。首先，建树的话与普通线段树无异，不过是建立一棵空树。然后对于每一个操作，我们都要首先传入前后两个时刻的root，利用传入的root我们可以让新操作完毕后的树继承之前一个操作完毕后的树的信息。在递归过程的每一步，我们首先就是让T[i]=T[old]，即继承上一个操作的信息。然后每次操作只往需要修改的分支取走，对应的old也要往修改的分支去跳。如此，我们可以保证，新产生的logN个点即继承了上一个操作的信息，完成了不变节点的共用，也达到了对需要修改节点的修改。具体实现的话见后续的博文。