主席树的个人理解

主席树，是一个可以以优良性能去做一个可持久化数据的数据结构。虽时间变得较少，但空间的消耗量是在是难以承受其他的东西。

主席树的一些基础知识

离散化

因为在题目中，为了让选手使用主席树，必定会将数据范围开的极大，但实际数字个数又相对于范围来说很小。 这时候我们不可能开一个极大的线段树（因为本来空间就不够用，还这么浪费），所以就无可避免的用到了离散化这个小小的技巧。 在C++库函数中，有一个函数叫做unique()。它的作用是去掉在地址为a到a+n中，相邻的量是否重复：是，就将其放置到这段地址的最后。 简单的来说，就是将一个排完序后的数组去重，返回没有重复内容的最后地址。 用法如下： 无重复元素的最后地址【返回的值】=unique (开始地址，结束地址) 该函数stl和数组均可使用

历史版本的作用

这么多棵线段树，我们也不可能建立多个结构体来保存。我们可以把所有线段树的节点全部放在tree结构体中，设当前有m个节点，每执行一次插入操作，新增了x个节点，则存放在tree中的第(m+1)个节点至第(m+x)个节点（当然也有别的编号方式）。同时，我们需要一个root数组，其中root[i]表示第i棵线段树的根节点的编号。 这样我们就构建完了，来想想——为什么需要历史版本？回到我们一开始的问题，求区间第k大，假设当前询问为求[x,y]的第k大，则我们所需要用到的线段树为第x+1棵到第y棵。从根节点开始，我们将第y棵树和第x+1棵树一一对应的节点所维护的值进行相减，其所得到的数就是在所询问的[x,y]中，当前节点表示的子区间的那几个数值在整个区间中出现的次数，用t表示，即t=root[y].[1,mid]-root[x-1].[1,mid]。先判断t是否大于k，如果t大于k，那么说明在区间[x,y]内存在[1,mid]的数的个数大于k，也就是第k大的值在[1,mid]中，否则在[mid+1,r]中。

缩小空间

其实必要的知识已经讲得差不多了，但是我们最后还要面临一个问题——加入一个数，就新建一棵线段树。我们假设有100000个数吧，且有100000次询问，试想这一大片庞大的线段树森林是要占用多大的内存？一定会MLE的（当然数据小就无所谓）。 我们有什么办法缩小空间需求？我们注意到，每次我们加入一个被离散化后的数x，则从根结点开始向下更新，我们真正相对于前面一棵线段树的差异之处是很少的！设有一颗[1,4]的线段树，若当前插入值为3，则[1,4]的左儿子[1,2]没有丝毫改动！如果又新建一个，完全是浪费。这样子，我们就有一个方法缩小冗余的空间了——将没有区别的部分直接指回去！

主席树的一些操作

单点更新

我们要修改一个叶子结点的值，并且不能影响旧版本的结构。 在从根结点递归向下寻找目标结点时，将路径上经过的结点都复制一份。 找到目标结点后，我们新建一个新的叶子结点，使它的值为修改后的版本，并将它的地址返回。 对于一个非叶子结点，它至多只有一个子结点会被修改，那么我们对将要被修改的子结点调用修改函数，那么就得到了它修改后的儿子。 在每一步都向上返回当前结点的地址，使父结点能够接收到修改后的子结点。 在这个过程中，只有对新建的结点的操作，没有对旧版本的数据进行修改。

区间查询

从要查询的版本的根节点开始，像查询普通的线段树那样查询即可。

查询[1,n]中的第K小值

我们先对数据进行离散化，然后按值域建立线段树，线段树中维护某个值域中的元素个数。 在线段树的每个结点上用cnt记录这一个值域中的元素个数。 那么要寻找第K小值，从根结点开始处理，若左儿子中表示的元素个数大于等于K，那么我们递归的处理左儿子，寻找左儿子中第K小的数； 若左儿子中的元素个数小于K，那么第K小的数在右儿子中，我们寻找右儿子中第K-(左儿子中的元素数)小的数。

查询区间[L,R]中的第K小值

我们按照从1到n的顺序依次将数据插入可持久化的线段树中，将会得到n+1个版本的线段树（包括初始化的版本），将其编号为0~n。 可以发现所有版本的线段树都拥有相同的结构，它们同一个位置上的结点的含义都相同。 考虑第i个版本的线段树的结点P，P中储存的值表示[1,i]这个区间中，P结点的值域中所含的元素个数； 假设我们知道了[1,R]区间中P结点的值域中所含的元素个数，也知道[1,L-1]区间中P结点的值域中所包含的元素个数，显然用第一个个数减去第二个个数，就可以得到[L,R]区间中的元素个数。 因此我们对于一个查询[L,R]，同步考虑两个根root[L-1]与root[R]，用它们同一个位置的结点的差值就表示了区间[L,R]中的元素个数，利用这个性质，从两个根节点，向左右儿子中递归的查找第K小数即可。