维护带修改区间 K 小值

就是在原来的主席树模板上加上一条将x上的值修改为k

待我们仔细想想之前静态的区间Kth怎么实现的...


我们仍然需要维护前缀和,而只是在以前的代码里面加上单点修改的操作,那么你要每次要修改的前缀和就有了n*2logn , 这样显然会TLE。

这里只需要把维护动态区间和的工作交给适合它的树状数组就行啦,修改点数变为logn, 复杂度为O( nlognlongn)

树状数组套动态开点的权值线段树,因为并不需要利用到之前的版本, 所以并不是主席树。关于权值线段树的部分,我会填坑的

//不会做啊!!!!!!

原文地址:https://www.cnblogs.com/tyner/p/11260552.html