主席树带修第k大
https://www.cnblogs.com/Empress/p/4659824.html 讲的非常好的博客
首先按静态第k大建立起一组权值线段树(主席树)
然后现在要将第i个值从a改为b，
由主席树前缀和的性质可知修改第i个值会对T[i]...T[n]棵权值线段树造成相同的影响
如果暴力进行维护必定超时
那么如何优化这种修改？
我们知道动态维护前缀和可以用bit在log时间内完成
那么对于动态维护具有前缀和性质的主席树，我们也可以套上bit来完成
update：将第i个值从a改成b
根据bit的原理，第i个元素的修改会影响第i+lowbit(i)个元素
那么现在第i棵树修改了，第i+lowbit(i)棵树也应该影响
即第i棵树的位置a -1，同样的第i+lowbit(i)棵树的位置a -1
同理这批树的位置b +1即可
query：询问区间[l,r]第k大元素
即求T[r]-T[l]的前缀和即可
查询时要把bit对应的修改套上
原文：https://www.cnblogs.com/zsben991126/p/10765363.html