权值线段树
2026-02-26
简介
在普通的线段树中,维护的区间只能在 [1∼n] 内,如果 n≤1e9 怎么办呢?这个时候就要引入权值线段树了。
在权值线段树中,每个节点代表的是一段值域,例如 [l∼r] 表示的就是 [l,r] 中的所有数。
很明显,我们并不能采用 u×2 的方式找儿子,因为 V(值域)很大,所以我们需要使用动态开点,这样只需要存储查询涉及到的 O(mlogV) 个节点(别忘了开四倍)。
也就是说,相比于传统的离散化后处理,权值线段树支持在线。
查询第 K 小
权值线段树有一个特殊的用处,由于一个节点直接代表一段值域,所以我们可以通过维护 cnt 来查询第 k 小的数。
在查询时,k≤cntl 向左找第 k 小;否则向右找第 k−cntl 小。
