所謂樹狀數組套權值線段樹，就是在樹狀樹組上套權值線段樹

（逃）

解析

如何解決靜態(tài)區(qū)間第k小？
使用主席樹就ok啦

辣么如何解決動態(tài)區(qū)間第k小嘞…

我們想想主席樹為啥不能解決動態(tài)區(qū)間第k小
因為如果改了一個點的值，后面所以的權值線段樹都需要修改
單次修改的時空復雜度為$nlogn$，無法承受

仔細想想，靜態(tài)的主席樹似乎就是一個關于值域的高級一點的前綴和
暴力修改前綴和當然是需要修改$O(n)$個了
但是既然是前綴和，我們?yōu)榫涂梢韵氲接脴錉顢到M優(yōu)化
這樣需要修改的東西就變成了$O(logn)$個了

具體的說，和樹狀數組的定義類似，第i棵權值線段樹維護的是$[i?lowbit(i)+1,i]$的值域
這樣單次修改只需要改log棵樹
時空復雜度$nlog{n}^2$
詢問的時候把對應的log棵樹都拿出來
一起算size就可以了
時間復雜度$nlog{n}^2$
可以說是很優(yōu)秀了
板子傳送門

代碼

#include<bits/stdc++.h> using namespace std; #define ll long long const int N=2e5+100; inline ll read(){ll x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-'0';c=getchar();}return x*f; } int n,m; int r[N],tot; struct node{int ls,rs,siz; }tr[N*300]; inline int New(){++tot;tr[tot].ls=tr[tot].rs=0;return tot; } #define mid ((l+r)>>1) inline void pushup(int k){if(k) tr[k].siz=tr[tr[k].ls].siz+tr[tr[k].rs].siz;return; } inline void upd(int &k,int l,int r,int p,int v){if(!k) k=New();if(l==r){tr[k].siz+=v;return;}if(p<=mid) upd(tr[k].ls,l,mid,p,v);else upd(tr[k].rs,mid+1,r,p,v);pushup(k);//printf(" k=%d (%d %d),siz=%d\n",k,l,r,tr[k].siz); } int a[N],q[N],cnt; inline void change(int p,int v){for(int i=p;i<=n;i+=i&-i){upd(r[i],1,cnt,a[p],-1);upd(r[i],1,cnt,v,1);}a[p]=v;return; } vector<int>L,R; void get(int l,int rr){L.clear();R.clear();for(int i=l-1;i;i-=i&-i) L.push_back(r[i]);for(int i=rr;i;i-=i&-i) R.push_back(r[i]);return; } int ask(int l,int r,int k){if(l==r) return q[l];int num=0;for(int i=0;i<R.size();i++){int x=R[i];num+=tr[tr[x].ls].siz;}for(int i=0;i<L.size();i++){int x=L[i];num-=tr[tr[x].ls].siz;}if(k<=num){for(int i=0;i<R.size();i++){R[i]=tr[R[i]].ls;}for(int i=0;i<L.size();i++){L[i]=tr[L[i]].ls;}return ask(l,mid,k);}else{for(int i=0;i<R.size();i++){R[i]=tr[R[i]].rs;}for(int i=0;i<L.size();i++){L[i]=tr[L[i]].rs;}return ask(mid+1,r,k-num);} } char op[N]; int x[N],y[N],k[N]; int main(){n=read();m=read();for(int i=1;i<=n;i++){a[i]=read();q[++cnt]=a[i];}for(int i=1;i<=m;i++){scanf(" %c",&op[i]);x[i]=read();y[i]=read();if(op[i]=='Q') k[i]=read();else q[++cnt]=y[i];}sort(q+1,q+1+cnt);cnt=unique(q+1,q+1+cnt)-q-1;for(int i=1;i<=n;i++){//printf("\ni=%d\n",i);a[i]=lower_bound(q+1,q+1+cnt,a[i])-q;for(int p=i;p<=n;p+=p&-p){//printf("upd:%d\n",p);upd(r[p],1,cnt,a[i],1);}}//for(int i=1;i<=n;i++) printf("i=%d rot=%d siz=%d\n",i,r[i],tr[r[i]].siz);for(int i=1;i<=m;i++){if(op[i]=='Q'){get(x[i],y[i]);printf("%d\n",ask(1,cnt,k[i]));}else{y[i]=lower_bound(q+1,q+1+cnt,y[i])-q;change(x[i],y[i]);}}return 0; }

總結

以上是生活随笔為你收集整理的动态区间第k小：树状数组套权值线段树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。