或称可持久化的 线段树。
m 次修改会有 m + 1 个版本, 在修改时对于变化的节点会新建一个节点, 耗费的总空间为 , 因为根节点会有多个, 故不能采用以前堆的方式来固定下标存储, 而是要用指针的方式
每个节点存储 l,r 表示左右子节点的下标, cnt 表示当前区间中有多少个数。而当前节点的区间边界就直接用函数参数传递, 就像以前做的那样
可持久化线段树有很多个版本, 难以处理懒标记, 也因此难以处理区间修改, 不过可以处理为永久性懒标记, 但这种解法很局限, 只能像扫描线一样解决特定问题。
依然是新建一个节点存储变化的节点, 对应旧的子树就用指针指回上一个版本的节点。
题目
| 题目 | 简介 |
|---|---|
| 第K小数 |