# 可持久化线段树

# 介绍

略

# 应用

# 无修改求区间第 $k$ 大

1. 首先, 给你一颗值为横坐标的线段树, 每个节点上存着该值出现了多少次, 这样的一颗线段树你会求区间 $k$ 大值吧. 二分即可.
2. 然后, 假设区间是数组 $arr[n]$, 区间长度是 $n$, 那么给你 $n$ 颗线段树, 第 $i$ 颗线段树是第 $i-1$ 颗线段树插入 $arr[i]$ 得到.
3. 如果你有了这 $n$ 颗线段树, 想求区间 $[l,r]$ 中的第 $k$ 大值, 那么你需要在第 $r$ 颗和第 $l-1$ 颗线段树的差线段树上作二分, 就可以求得区间第 $k$ 大值.
4. 差线段树很好理解, 比如你有一个部分和数组 $sum$, $sum[r]-sum[l-1]$ 就是部分和的差, 代表区间 $[l,r]$ 的和,差线段树同理.
5. 现在, 可持久化线段树出现为你解决最后一个问题, 空间问题. 内存很小, 不能够存下 $n$ 颗线段树. 但是, 第 $2$ 条中提到, 由于第 $i$ 颗线段是是第 $i-1$ 颗线段是插入仅一个值得到的, 两颗线段树的区别不大, 仅有 $\log(n)$ 个节点发生了改变, 我们仅仅需要记录这 $\log(n)$ 的数据就可以记录这个增量, 这就是可持久化线段树.

作者：Comzyh
链接：https://www.zhihu.com/question/25959110/answer/37947531
来源：知乎
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。