树状数组/线段树套平衡树
-
线段树每个节点开一棵平衡树，空间复杂度 $O(n\log n)$。
查询排名，找到 $O(\log n)$ 棵平衡树查询，时间复杂度 $O(\log^2n)$。
查询数值，通过查排名二分，时间复杂度 $O(\log^3n)$。
单点修改，时间复杂度 $O(\log^2n)$。
查询前驱，时间复杂度 $O(\log^2n)$。
查询后继，时间复杂度 $O(\log^2n)$。
总时间复杂度 $O(n\log^2n + m\log^3n)$。
树状数组/线段树套权值线段树
-
通过 dfs 序可以将问题转化为矩阵加，查询某点的 $k$ 小值。整体二分即可。
-
如果不带修，那么可以树上主席树，查询时差分一下即可。
发现修改的每次会对一段区间的线段树造成影响，那么套一个树状数组即可。