权值线段树与动态开点线段树

权值线段树（维护一段值域）

用线段树维护桶

实质上是维护一段值域中数字出现次数

例：\(1,5,4,6,7,3,8,4,5,6\)；

根： \(1-8\)；
左儿子： \(1-4\)；
右儿子： \(5-8\)；

询问目前出现第 \(k\) 小数字

从根节点出发，如果根节点权值 \(>k\) 则证明存在第 \(k\) 小；

以此类推

问：如果值域很大，线段树炸了怎么办

动态开点线段树

最初只建根节点，代表整个区间；
需要访问某棵子树（区间）时，再建代表该区间的节点；

复杂度对比：假设某值域为 \(1-w\)，普通建树要开 \(4w\) 的空间，空间复杂度 \(O(mlog_w)\)；
而动态开点线段树复杂度与操作次数有关，为 \(O(mlog_w)\)。

注：动态开点线段树节点编号是按开点顺序排的。
所以我们用 \(ls,rs\) 表示左、右儿子编号。

PS:动态开点空间复杂度为 \(O(mlog_w)\) 一般来说，为保证不溢出，开到 \(mlog_{w+2}\) 比较合适，其中 \(w\) 是值域，例如若值域是 \(10^5\)，那么 \(log_w≈17\)，则开到 \(19\) 即可。