可持久化线段树
2026-01-02
Intro
线段树和字典树一样,由于线段树同样满足插入节点后结构不变的性质,所以可以进行可持久化。
一个普通线段树的插入会涉及到 O(logn) 个节点,所以可持久化线段树也只会涉及到 O(logn) 个节点。
由于只需要额外存储不同的点,所以新节点的某个分支会指向原节点的某个分支。
AcWing 255. 第K小数
题目传送门
首先来考虑怎么用线段树求原序列 l 到 r 的第 k 小数。
容易发现,直接存储下标的线段树效率不高,而原序列又是不变的,所以可以使用动态开点的权值线段树。
具体的,我们可以在线段树中维护 l,r 分别表示这个节点左右儿子编号,cnt 表示这个区间的长度。
当要查询第 k 小的数时,记当前区间为 u,若 k≤cntl,则进入左子树;否则将 k−cntl 后进入右子树(预先进行离散化)。
考虑加入 [l,r] 的限制,容易发现只要进行可持久化后可以直接支持 r 的限制,且 l 的限制其实相当于第 r 次减去 l−1 次的权值,直接做即可。
