可持久化线段树（主席树）（图文并茂详解）【poj2104】【区间第k大】_区间第k大ext

[pixiv] https://www.pixiv.net/member_illust.php?mode=medium&illust_id=63740442
向大(hei)佬(e)实力学(di)习(tou)

主席树主要用于处理区间的问题，其中区间不一定是单纯的区间，还是可以将题目中的一些信息转化一下（如 操作、时间等），即需要查询区间信息的数据，还需要用线段树用的题目，就可以用主席树。
以前有畏难心理，总觉得主席树好复杂，各种逃避。后来再次学习，总算是学会了基础的东西。

主席树通常是前缀和和线段树的结合，下面以一道经典题：区间第k大 为例

第k大，想到用值域线段树。区间可以转化为前缀，相减即可。即对每一个前缀节点建线段树，但如果暴力建，就完蛋了（^10），完美爆空间

仔细一想，每一个线段树和前一个相比，其实只修改了一个点。我们只需要新建树根到新增叶子节点路径上的点就可以了，其他的指向前一棵树的对应位置
放一张图来理解的更直观一些（灰色格子是虚点）

由此可见，空间复杂度为n*logn，可以接受
建树代码

void insert(Node *&ndn,Node *ndp,int le,int ri,int pos){
  //ndn当前的节点,注意要加&修改.ndp前一个节点，同步
    ndn=newnode();
    ndn->sum=ndp->sum+1;
    if(le==ri) return ;
    ndn->ls=ndp->ls,ndn->rs
1
2
3
4
5
6