权值线段树

donotctjuntilAFO · 2023-04-15 08:12:23 · 算法·理论

定义

将序列的数出现的个数用线段树维护就是权值线段树。

通俗地讲，就是将序列开个桶再用线段树维护。

权值线段树只关心数出现的个数 。

用途

可以解决插入，删除，第 k 小的数，数的排名等问题。

因此权值线段树可以解决大部分平衡树的问题。

当值域太大时，可以用动态开点权值线段树。

插入

将对应位置加 1 即可。

删除

将对应位置减 1 即可。

第 k 小的数

在线段树上二分即可。

代码：

int kth(int k,int l,int r,int x){
    if(!x)
        return -1;
    if(l==r)
        return l;
    int mid=l+r>>1;
    if(k<=tree[tree[x].ls].val)
        return kth(k,l,mid,tree[x].ls);
    else
        return kth(k-tree[tree[x].ls].val,mid+1,r,tree[x].rs);
}

数的排名

就是查询这个数之前的个数

代码：

int rnk(int l,int r,int ll,int rr,int x){
    if(!x)
        return 0;
    if(l<=ll&&rr<=r)
        return tree[x].val;
    int ans=0;
    int m=ll+rr>>1;
    if(l<=m)
        ans+=rnk(l,r,ll,m,tree[x].ls);
    if(r>m)
        ans+=rnk(l,r,m+1,rr,tree[x].rs);
    return ans;
}

例题

1【模板】普通平衡树

模板，不解释。

代码：

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
const int N=100005,MAX=10000000;
struct node{
    int ls,rs,val;
}tree[N<<5];
int n,rt,cnt;
void update(int p,int v,int l,int r,int &x){
    if(!x)
        x=++cnt;
    if(l==r){
        tree[x].val+=v;
        return; 
    }
    int mid=l+r>>1;
    if(p<=mid)
        update(p,v,l,mid,tree[x].ls);
    else
        update(p,v,mid+1,r,tree[x].rs);
    tree[x].val=tree[tree[x].ls].val+tree[tree[x].rs].val;
}
int kth(int k,int l,int r,int x){
    if(!x)
        return -1;
    if(l==r)
        return l;
    int mid=l+r>>1;
    if(k<=tree[tree[x].ls].val)
        return kth(k,l,mid,tree[x].ls);
    else
        return kth(k-tree[tree[x].ls].val,mid+1,r,tree[x].rs);
    return -1;
}
int rnk(int l,int r,int ll,int rr,int x){
    if(!x)
        return 0;
    if(l<=ll&&rr<=r)
        return tree[x].val;
    int ans=0;
    int m=ll+rr>>1;
    if(l<=m)
        ans+=rnk(l,r,ll,m,tree[x].ls);
    if(r>m)
        ans+=rnk(l,r,m+1,rr,tree[x].rs);
    return ans;
}
int main(){
    scanf("%d",&n);
    while(n--){
        int op,x;
        scanf("%d%d",&op,&x);
        if(op==1)
            update(x,1,-MAX,MAX,rt);
        else if(op==2)
            update(x,-1,-MAX,MAX,rt);
        else if(op==3)
            printf("%d\n",rnk(-MAX,x-1,-MAX,MAX,rt)+1);
        else if(op==4)
            printf("%d\n",kth(x,-MAX,MAX,rt));
        else if(op==5)
            printf("%d\n",kth(rnk(-MAX,x-1,-MAX,MAX,rt),-MAX,MAX,rt));
        else
            printf("%d\n",kth(rnk(-MAX,x,-MAX,MAX,rt)+1,-MAX,MAX,rt));
    }
    return 0;
}