题解 P3834 【【模板】可持久化线段树 1（主席树）】

**学习可持久化线段树之前一定要学懂线段树，大家可以看看我转载的一篇博客（http://blog.csdn.net/a1351937368/article/details/78884465）** 学习主席树的时候全是看的其他人的博客学的，但是觉得好多人写的博客很乱，看博客的时候感觉没什么头绪，现在终于搞懂了主席树，想自己写一些东西让其他人能很轻松的看懂主席树到底是什么 **主要思想**：主席树是利用函数式的编程思想使得线段树支持查询历史版本，同时充分利用他们之间的共同数据来减少时间和内存消耗的数据结构（这些东西不理解没什么关系，到最后慢慢就懂了）一棵线段树的节点维护的是当前节点对应的区间信息，若每次区间不同则处理较为困难，，例如频繁的询问区间第K大元素（较为简单的思想是根据归并排序思想实现的归并树，但是时空复杂度都较高） **第一部分.静态主席树** 发明者的原话：“对于原序列的每一个前缀[1···i]建立出一棵线段树维护值域上每个数出现的次数，则其树是可减的” 可以加减的理由：主席树的每个节点保存的是一颗线段树，维护的区间信息，结构相同，因此具有可加减性（**关键**） 首先开一个数组t[n]，存储内容为a中排序并去重的值（类似于离散化），每棵线段树维护的内容是a1...ai此区间中的树在t[n]中出现的次数 **举个栗子** an：4 1 1 2 8 9 4 4 3 将序列排序并去重后得到t[n]： tn：1 2 3 4 8 9 对前缀a[1...9]建树，1\*2，2\*1，3\*1，4\*3，8\*1，9\*1，每个数出现的次数即为线段树维护的值，树中每个节点表示t[i,j],中的数字在a[1...9]中出现的次数 建树： ![此树为a[1...9]为前缀即整个对序列信息所建立的树](http://img.blog.csdn.net/20171231111359520?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvYTEzNTE5MzczNjg=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast) **思考**如何求出区间第K大值，例如求a[1,9],中第六大的数 根节点左儿子有四个元素，则第六大的元素一定在右儿子中，利用递归的思想将问题转化为求区间a[1,9]中去除t[1],t[2],t[3],后的第二大数，此时其左儿子即区间[4.5]中有四个元素，4>2，所以第二大数一定在左儿子中，递归进入左儿子中所以所求的数就是除去t[1],t[2],t[3],t[6],后的第二大数，最后区间[4,4]中有三个元素，3>2，所以区间第二大数一定在区间[4,4]中即t[4]=4,所以求得的a[1,9]的第六大值。 若需要求区间[L,R]中的第K大值 对于任意的i，a[1,i]都有一颗树，则区间[L,R]中第K大值与求a[1,R]类似，由于其具有可减性，只要在递归结束时减去a[1,L-1]所在的树对应的部分即可，例如a[L,R]，小于t[mid]的数有六个(mid=(L+R)/2)在a[1,L-1]小于t[mid]的数有两个，则在a[L,R]小于t[mid]的数有6-2=4个，递归过程与上面类似（思想类似一维前缀和） 但是对于每一个前缀分别建立一棵线段树，空间复杂度极高，会MLE，为了解决这个问题我们先画出a[1,5],a[1,6],a[1,7],a[1,8]四个前缀的线段树，如下： ![[1,5]](http://img.blog.csdn.net/20180104123950066?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvYTEzNTE5MzczNjg=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast)[1,5] ![[1,6]](http://img.blog.csdn.net/20180104124542853?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvYTEzNTE5MzczNjg=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast)[1,6] ![[1,7]](http://img.blog.csdn.net/20180104124829000?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvYTEzNTE5MzczNjg=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast)[1,7] ![[1,8]](http://img.blog.csdn.net/20180104125108139?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvYTEzNTE5MzczNjg=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast)[1,8] 观察[1,8]和[1,9]我们发现例如[1,8],[1,9]有许多地方信息相同，其中包含了大量重复信息，占用了多余的空降，如何避免空间的浪费呢？例如[1,8].[1,9]在建a[1,9]时根节点直接向a[1,8]的右子树连一条边，同理对于其左儿子节点，它的左子树部分也是相同的（此时视[1,3]为根节点）因此连接一条边即可，如此我们只增加了三个节点就保存了两棵树的全部信息。  因此在之前基础上建树只需开一个数组储存两个箭头所指的位置，接着向下遍历就是一棵完整的线段树增加节点为[9],[1],[4]三个节点。  **静态主席树的一些点** 1. 建树时首先需要建一棵空的线段树，即最原始的主席树，此时主席树只含有一个空的节点，之后依次对原序列按某种顺序更新，就是将原序列加入到相应的位置 2.主席树是一种特殊的线段树集，它包含了所有线段树的优势，并且可以保存历史状态，主席树查找和更新的时空复杂度都为O(nlogn)且总空间复杂度为O(nlogn+nlogn)前者为空树的复杂度，后者为更新n次的空间复杂度，缺点是空间损耗巨大 3.主席树可以处理区间[L,R]中介于[x,y]的值的问题 4.若增加空间垃圾回收则可以使空间复杂度降低一个log **例题** [POI]2014 KUR-Couriers(https://www.luogu.org/problemnew/show/3567) 给定长为N的序列，m组询问，每次询问一个区间[l,r]，是否存在一个数在[l,r]中出现次数大于(l-r+1)/2，若存在输出这个数，否则输出0(n,m<=500000) **题解** 裸的线段树模板，直接把读入的数字插入到主席树中，对于每个询问[i,j]在[1,n]中看小于mid(mid=(i+j)/2)的数字有多少个，若每个数的二倍不大于j-i+1则[L,mid]中就不存在，不然再去看大于mid的数字有多少个，若两个均不行输出0. 举个栗子：1 1 3 2 3 4 3 查询区间[1,7] 首先区间二分：重点a[mid]=2 小于-> 4<7-1+1 大于-> 8<7-1+1 区间右移，如此反复，最后区间二分到1 1 3 [2 3 4 3] 小于-> 2<7-4+1 大于-> 2<7-4+1 均不满足，输出0 **第二部分·动态主席树** 动态主席树就是在静态主席树基础上增加了一批用树状数组维护的线段树 **举个栗子** 5 3 3 2 1 4 7 Q 1 4 3 询问区间[1,4]的第三小数 C 2 6 将第二个数变为6 Q 2 5 3 n是原序列个数 T[i]表示第i棵线段树的根节点编号 S[i]表示树状数组思维建的第i棵线段树的根节点编号 L[i]表示节点i的左子节点编号 R[i]表示节点i的右子节点编号 sum[i]表示节点i对应区间中数的个数。 这里离散化建树过程和静态主席树有一点不同，我们必须把所有询问先存起来并且把改变的数也加入到原序列中再离散化建树，会导致空间复杂度和静态有所区别。所以这里我们离散化后序列为3 2 1 4 6 5分别对应原序列的3 2 1 4 7和改变后的6。 之后同静态一样建空树，按原序列前缀建树 接下来就是重点了，对于题目给出的修改操作，我们新建一批线段树来记录更新，这些线段树以树状数组的思维来维护。 一开始，S[0]、S[1]、S[2]、S[3]、S[4]、S[5] （注意一共有n+1个 即 0到n）(树状数组的每个节点)这些都与T[0]相同(也就是每个节点建了一棵空树)。 对于C 2 6 这个操作， 我们只需要减去一个2，加上一个5（对应改变后的6）即可。 这个更新我们按树状数组的思想更新，比如这里的减2，我们要从i=2（原序列中第2个数2在离散化后序列中的位置）即S[2]开始更新，并往上lowbit(i)直到大于5，这里我们会更新S[2]和S[4]。 边看图边理解（这个图最后应该是在节点5那里减1）  对于加5同样是从S[2]开始更新 （这个图最后应该是在节点10那里加1）  这样我们查询的时候T[]和静态一样，再按树状数组的思维加上S[]就可算出每个节点对应区间中数的个数，再按静态的思想查询即可。 **例题** Luogu P3168 [CQOI]任务查询系统 (https://www.luogu.org/problemnew/show/3168) 有n个任务分别持续m秒，每个任务从si秒开始到ei秒结束且有一个优先级pi 有m个询问需要回答第xi秒时正在执行任务中优先级前ki小的和，并且强制在线 输入格式： 第一行正整数mn，表示任务总数和时间范围，之后m行 每行三个数si，ei，pi，描述一个任务，接下来n行，每行四个数xi，Ai，Bi，Ci查询参数Ki由公式ki=1+(Ai+Pre+Bi)modCi得到，其中pre表示上一次查询的结果，pre初始值为1 pi<=1e7 **题解** 由于时间在变化，任务会开始或结束，由于想知道任意时刻任务执行情况，需要用到可持久化数据结构，可以维护一个主席树 先在第0s创建一个空版本，将每一个任务分为两步操作 1任务在si秒插入 2任务在ei+1秒删除 在插入删除时要新建节点 由于权值太大，需要对数据离散化