可持久化线段树

简介

在对线段树进行单点修改的时候，每次不修改当前节点，转而新建一个节点。
这样每次修改只会新建O(log⁡n)O(\log n)个节点，空间上可以接受。
并且可以随时访问历史版本的线段树，有一些奇妙的用途。

按权值建线段树

按位置建线段树：线段树的第ii个点表示数组中aia_i是什么。
按权值建线段树：线段树的第ii个点表示值ii出现了多少次。
然后将数组中的值一个一个添加到线段树中，相当于可以随时访问到
数组的一个前缀中某个值（或者某个值的区间）出现了多少次。
在此基础上，就可以进行区间询问第kk大了。

用途

最基本的用途是可以询问区间第kk大，但是也可以处理其他类型的询问

  1. 区间第kk大是多少？
  2. 询问xx是区间第几大？
  3. 区间内最大的kk个数字是多大？
  4. 在区间内选择一些数字，使得他们的和不超过xx，最多选择多少个？

代码

参考题目



spoj COT


codechef FRBSUM


      

      
    

  1. 可持久化线段树

      

    1. 简介
      2. 

    2. 按权值建线段树
      3. 

    3. 用途
      4. 

    4. 代码
      5. 

    5. 参考题目
      6. 

    

    2. 




      ≡