所謂求動態(tài)第K大是支持查詢區(qū)間第k大,同時還支持序列的單點修改泼掠。
我們知道,如果修改了arr[i],那么對于靜態(tài)主席樹來說,它影響的是tree[i],tree[i+1]...tree[n];有一個辦法是對這些樹全部進行更新,但是這樣的復(fù)雜度會很高;同時,我們注意到,有一個很適合單點更改和求序列和的數(shù)據(jù)結(jié)構(gòu),那就是樹狀數(shù)組,;所以我們可以這樣做:對于原序列,我們建立靜態(tài)主席樹,對于要修改的節(jié)點,我們用樹狀數(shù)組來維護,每個樹狀數(shù)組的節(jié)點都是線段樹。
比如原序列:1 5 6 2 3 9 8,現(xiàn)在我要把第四位2改為7,理論上說,我們修改一個數(shù)字,首先要消除原數(shù)字對序列的影響,再添加新的數(shù),然后再產(chǎn)生新的影響;現(xiàn)在2對序列的影響是:第四位以及到最后一位的對應(yīng)的所有前綴樹,每個前綴樹中包含2的區(qū)間對應(yīng)的節(jié)點與原來比都加上了1,要消除這些影響,我們要對4-n顆前綴樹的所有包含2的區(qū)間的節(jié)點都要減去1,然后再把第四位改為7,再對第4-n顆前綴樹的所有包含7的區(qū)間的節(jié)點都要加上1,到此,更新就結(jié)束了冬筒。
只不過,我們修改的時候是利用樹狀數(shù)組,所以修改的樹不再是4-n顆樹,而是x1=4,x2=4+lowbit(x1),x3=x2+lowbit(x2)....n顆樹,對修改的次數(shù)為原來的log2n,同時空間復(fù)雜度也減少了
其實動態(tài)主席樹的空間消耗還是很大的瞪慧，比如上次修改了序列的第i位或者修改某位沿著lowbit上升時經(jīng)過了第i位髓考，那么修改的時候是會對i重新建樹的,用新的樹代替了原來的樹,大概原理就是這樣。修改的次數(shù)越多,新建的樹越多,消耗空間越多弃酌。
當(dāng)然了,用數(shù)組開的靜態(tài)區(qū)間消耗的空間是固定的,但是它的剩余空間會隨著修改的增加越來越少氨菇。
Dynamic Rankings
題意:
給你一個長度為n(1 <= N <= 50,000)的序列。序列中每個值都不超過1e9.然后有m(1 <= M <= 10,000)次操作妓湘。
1.Q i j k 詢問i,j間第k大的值查蓉。
2.C i val 把序列的第i個值改成val。
#include<cstdio>
#include <algorithm>
using namespace std;
const int MAXN = 60010;
int n,m,tot,cnt,idx;
int arr[MAXN], cpy[MAXN];//原序列
//root為靜態(tài)主席樹的根節(jié)點
int root[MAXN], lson[MAXN*40], rson[MAXN*40],sum[MAXN*40];
//S為動態(tài)主席樹的根節(jié)點,use是用來存儲更新時,沿著lowbit上升時經(jīng)過的樹
int S[MAXN],use[MAXN];
int build(int l,int r)
{
int rt = tot++;
sum[rt] = 0;
if(l != r)
{
int mid = (l+r)>>1;
lson[rt] = build(l,mid);
rson[rt] = build(mid+1,r);
}
return rt;
}
//以last這棵樹為參照,新建一棵樹,即新建的樹有一部分節(jié)點共用last這棵樹
int update(int last,int pos,int val)
{
int rt = tot++, tmp = rt;
int l = 0, r = cnt-1;
sum[rt] = sum[last] + val;
while(l < r)
{
int mid = (l+r)>>1;
if(pos <= mid)
{
lson[rt] = tot++; rson[rt] = rson[last];
rt = lson[rt]; last = lson[last];
r = mid;
}
else
{
rson[rt] = tot++; lson[rt] = lson[last];
rt = rson[rt]; last = rson[last];
l = mid+1;
}
sum[rt] = sum[last] + val;
}
return tmp;
}
int lowbit(int x)
{
return x&(-x);
}
void add(int x,int pos,int val)
{
while(x <= n)
{
S[x] = update(S[x],pos,val);
x += lowbit(x);
}
}
int getSum(int x)
{
int ret = 0;
while(x > 0)
{
ret += sum[lson[use[x]]];
x -= lowbit(x);
}
return ret;
}
int query(int left,int right,int k)
{
int left_root = root[left-1];
int right_root = root[right];
int l = 0, r = cnt-1;
for(int i = left-1;i;i -= lowbit(i)) use[i] = S[i];
for(int i = right;i ;i -= lowbit(i)) use[i] = S[i];
while(l < r)
{
int mid = (l+r)>>1;
int tmp = getSum(right) - getSum(left-1) + sum[lson[right_root]] - sum[lson[left_root]];
if(tmp >= k)
{
r = mid;
for(int i = left-1; i ;i -= lowbit(i))
use[i] = lson[use[i]];
for(int i = right; i; i -= lowbit(i))
use[i] = lson[use[i]];
left_root = lson[left_root];
right_root = lson[right_root];
}
else
{
l = mid+1;
k -= tmp;
for(int i = left-1; i;i -= lowbit(i))
use[i] = rson[use[i]];
for(int i = right;i ;i -= lowbit(i))
use[i] = rson[use[i]];
left_root = rson[left_root];
right_root = rson[right_root];
}
}
return l;
}
int getId(int x)
{
return lower_bound(cpy,cpy+cnt,x)-cpy;
}
struct Node
{
int kind;
int l,r,k;
}que[10010];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
tot = 0;
cnt = idx =0;
for(int i = 1;i <= n;i++)
{
scanf("%d",&arr[i]);
cpy[idx++] = arr[i];
}
char op[10];
//至于為什么要先把所有的修改的節(jié)點找出來,才進行建樹,那是因為只有知道序列的范圍才可以建樹,無他
for(int i = 0;i < m;i++)
{
scanf("%s",op);
if(op[0] == 'Q')
{
que[i].kind = 0;
scanf("%d%d%d",&que[i].l,&que[i].r,&que[i].k);
}
else
{
que[i].kind = 1;
scanf("%d%d",&que[i].l,&que[i].r);
cpy[idx++] = que[i].r;
}
}
sort(cpy,cpy+idx);
cnt = unique(cpy,cpy+idx) - cpy;//離散化
root[0] = build(0,cnt-1);//建立空樹
for(int i = 1;i <= n;i++)
root[i] = update(root[i-1],getId(arr[i]),1);//建立靜態(tài)主席樹
for(int i = 1;i <= n;i++)
S[i] = root[0];//為每個樹狀數(shù)組根節(jié)點初始化
for(int i = 0;i < m;i++)
{
if(que[i].kind == 0)
printf("%d\n",cpy[query(que[i].l,que[i].r,que[i].k)]);
else
{
add(que[i].l,getId(arr[que[i].l]),-1);//先消除影響
add(que[i].l,getId(que[i].r),1);//再新建影響
arr[que[i].l] = que[i].r;
}
}
}
return 0;
}
