Kth

https://www.luogu.com.cn/problem/solution/P2617

1、静态整体Kth

滑稽吧...sort一遍就好了。

时间复杂度O(nlogn)O(nlogn) 空间复杂度O(n)O(n)

2、动态整体Kth

离散化后开一棵权值线段树，每个位置的值表示这个位置对应的那个数（离散化后的）有多少个，向上维护和；

查询时先查询左子树和sum，比较k和sum的大小：若k<=sum则说明第k小数在左子树中，递归查询左子树；

否则，这个数对应的就是右子树中第k-sum小的数，k-=sum，递归查询右子树。

时间复杂度O(nlogn)O(nlogn) 空间复杂度O(n)O(n)

3、静态区间Kth

对每个点以其前缀开一棵权值线段树，那么任意一段区间均可以表示成为两棵权值线段树作差，即R位置的线段树减去L-1位置上的线段树

每个点开一棵线段树空间复杂度O(n^2)O(n 2 )，MLE，考虑到后一个位置相比于前一个位置的更改只有lognlogn个节点，所以使用主席树

时间复杂度O(nlogn)O(nlogn) 空间复杂度O(nlogn)O(nlogn)

4、动态区间Kth(就是本题辣) luogu P2617 Dynamic Rankings

还是要想办法维护前缀和。如果只是同3、的前缀和的话，就要对前缀和进行O(nlogn)O(nlogn)的单次修改，显然TLE。

这里考虑用树状数组维护前缀和。修改时，可以只修改lognlogn个位置，复杂度O(log^2n)O(log 2 n)；

查询时，依旧是R位置减去L-1位置，这时候不再是两棵线段树作差，而是log棵线段树与log棵线段树作差；跳的时候，log个节点一起跳到左子树/右子树

时间复杂度O(nlog^2n)O(nlog 2 n) 空间复杂度O(nlogn)O(nlogn)