权值线段树

Rorre_y · 2025-01-04 20:45:18 · 算法·理论

作者注：不建议没有oi基础的同学阅读此文章。

权值线段树的基础与运用

1.什么是权值线段树

顾名思义，权值线段树是线段树的一种。

我们知道，线段树是一种可以用来实现区间操作的数据结构。其中存储的是区间内每个位置对应的值。权值线段树相当于普通线段树和桶排序的结合体，存储的是每个数字出现的次数。

因此，权值线段树可以看做是可以区间操作的桶排序。

2.权值线段树的原理

这部分内容部分引自某大佬的文章。

比如现在有一个数组

a=[1,1,2,2,2,3,4,5,6,7,8]

对于每个节点，初始时个数为 0：

把所有1插入：

类似的，插入所有2：

最后：

不难看出，权值线段树复杂度为\log \max{a}，其中\max{a} 为数组中最大的权值，即数字的最大值。相比于桶排序 \max{a} 的复杂度已经有了很大的进步。

3.如何使用权值线段树

因为缺乏模板题，所以借用别的题目粗略讲一下。

题目大意：

您需要动态地维护一个可重集合 M，并且提供以下操作：

向 M 中插入一个数 x。
从 M 中删除一个数 x（若有多个相同的数，应只删除一个）。
查询 M 中有多少个数比 x 小，并且将得到的答案加一。
查询如果将 M 从小到大排列后，排名位于第 x 位的数。
查询 M 中 x 的前驱（前驱定义为小于 x，且最大的数）。
查询 M 中 x 的后继（后继定义为大于 x，且最小的数）。

对于操作 3,5,6，不保证当前可重集中存在数 x。

分析题目：

使用桶排序必定超时，考虑权值线段树。

先用前缀和预处理。这里不做介绍。

对于操作 1 和 2，只要相应改变该权值对应的数量即可。

对于操作 3，将所有权值小于该值的数量求和即可。

对于操作 4，考虑二分查找，若左子树权值和小于等于排名，那么查找右子树，否则查找左子树。

对于操作 5、6，查找权值前后第一个数量不为 0 的权值即可。

4.代码

"Talk is cheap,show me the code."

代码来自上面那位大佬的文章。

由于该题需要离散化等操作，超出本文讨论范围，这里不细讲。

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    register int x=0;
    register bool f=0;
    register char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') f=1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<3)+(x<<1)+c-48;
        c=getchar();
    }
    return f?-x:x;
}
void write(int x){
    if(x<0) putchar('-'), x=-x;
    if(x>=10) write(x/10);
    putchar('0'+x%10);
}
const int maxn=111111;
struct seg{
    int v; 
}t[maxn<<3];
void pushup(int o){
    t[o].v=t[o<<1].v+t[o<<1|1].v;
}
void change(int o,int l,int r,int q,int v){
    if(l==r){
        t[o].v+=v;
        return ;
    }
    int mid=l+r>>1;
    if(q<=mid) change(o<<1,l,mid,q,v);
    else change(o<<1|1,mid+1,r,q,v);
    pushup(o);
}
int query_rnk(int o,int l,int r,int ql,int qr){
    if(ql<=l && r<=qr){
        return t[o].v;
    }
    int mid=l+r>>1,ans=0;
    if(ql<=mid) ans+=query_rnk(o<<1,l,mid,ql,qr);
    if(qr>mid) ans+=query_rnk(o<<1|1,mid+1,r,ql,qr);
    return ans;
}
int query_num(int o,int l,int r,int q){
    if(l==r){
        return l;
    }
    int mid=l+r>>1;
    if(t[o<<1].v>=q) return query_num(o<<1,l,mid,q);
    else return query_num(o<<1|1,mid+1,r,q-t[o<<1].v);
}
int lsh[maxn<<2],tot,n;
struct _node{
    int opt,val;
}node[maxn<<2];
int main(){
    n=read();
    for(int i=1;i<=n;i++){
        node[i].opt=read();
        node[i].val=read();
        if(node[i].opt==4) continue;
        lsh[++tot]=node[i].val;
    }
    sort(lsh+1,lsh+tot+1);
    tot=unique(lsh+1,lsh+1+tot)-lsh-1;
    for(int i=1;i<=n;i++){
        if(node[i].opt!=4) node[i].val=lower_bound(lsh+1,lsh+tot+1,node[i].val)-lsh;
        if(node[i].opt==1) change(1,1,tot,node[i].val,1);
        if(node[i].opt==2) change(1,1,tot,node[i].val,-1);
        if(node[i].opt==3){
            if(node[i].val==1){
                puts("1");
                continue;
            }
            printf("%d\n",query_rnk(1,1,tot,1,node[i].val-1)+1);
        }
        if(node[i].opt==4){
            printf("%d\n",lsh[query_num(1,1,tot,node[i].val)]);
        }
        if(node[i].opt==5){
            int rk=query_rnk(1,1,tot,1,node[i].val-1);
            printf("%d\n",lsh[query_num(1,1,tot,rk)]);
        }
        if(node[i].opt==6){
            int rk=query_rnk(1,1,tot,1,node[i].val)+1;
            printf("%d\n",lsh[query_num(1,1,tot,rk)]);
        }
    }
    return 0;
}

完。

参考文献：

《浅谈权值线段树》——BFqwq

鸣谢：

指导老师：姚肖豪
主编：陈泽铭、陈庆桐、何增鑫
协助：郑其远、吕宝仑、许浚杰、黄欣桐