可持久化线段树

可持久化线段树

模板

在某一指定版本的单点查，单点修。

开 $m$ 棵线段树，每次修改复制后单点修。时间复杂度 $O(m(n+\log n))$，空间复杂度 $O(nm)$，不如暴力。

每次修改的时候，影响的点是 $\log n$ 级的，其余点均不受影响。因修改而新建线段树时，可以利用未修改的点，做到 $O(m\log n)$。

具体实现动态开点即可，空间复杂度 $O(m\log n+n)$，注意线段树自身的常数。

代码

静态 kth

模板

第 $l-1,r$ 棵线段树形态相同，可以相减得到区间答案。

离散化，二分答案，每次统计区间内小于他的个数。这个过程可以用可持久化线段树实现，时间复杂度 $O(m{\log }^{2}n)$。

事实上，这个过程可以做到 $O(m\log n)$。即查询时，记左子树区间的数量为 $L$。 $L\ge k$，则在左子树中继续找第 $k$ 大；否则右子树找第 $k-L$ 大。