浅谈权值线段树 & Luogu3369 题解

发布于 2020-12-21  400 次阅读


本文在作者的洛谷博客同步发布,Mathjax炸了可以去那里。

权值线段树(傻瓜式教程,超详细解析)

权值线段树,顾名思义,就是每个点代表的是一个权值出现的次数。

来看图(以离散化做法为例):

看懂这个图就很好理解权值线段树了。

其他的我们来看下面的例题理解:


来看一道模板题:

洛谷P3369 普通平衡树(离线做法)

维护一个支持一下操作的数据结构:

1.插入 $x$ 数

2.删除 $x$ 数(若有多个相同的数,只删除一个)

3.查询 $x$ 数的排名(排名定义为比当前数小的数的个数+1)

4.查询排名为 $x$ 的数

5.求 $x$ 的前驱(前驱定义为小于 $x$ ,且最大的数)

6.求 x 的后继(后继定义为大于 $x$ ,且最小的数)

免得各位看官再次翻上去,再放一遍图:

稍微讲解一下各种操作吧:(虽然我觉得有图就够了):

  1. 先对原序列离散化。
  2. 建树(虽然这时候这棵树没有值,但我习惯于对于每个点保存它的区间 $[l,r]$ 在递归求解的时候能少两个参数呢$QvQ$)。
  3. 插入操作:以上图中插入 $3$ 为例,我们找到 $3$ 离散化后对应的序号 $1$ ,然后跟普通线段树一样,找到,然后把对应的出现次数+1就可以了。
  4. 删除操作:和插入操作同理,只不过是把权值-1而已$QvQ$,在代码里我是用同一个函数 $modify$ 实现的。
  5. 找排名、前驱、后继:相关注释我放在代码注释里了,各位直接看代码就可以(我觉得结合代码食用会比较好一点嗷)。

另外:这里没有用动态开点线段树,用的是离散化。如果用动态开点,就是把建树的时候,id这个标号变量开成引用(&id),对于每个树的结点再开一个lson和rson,代表左右儿子,直接把id通过引用赋值上去即可。
想看的话可以看我的另外的博客(先咕着,之后会写的)。再对每个结点开一个Minval和Maxval代表对应区间的范围就好了(口胡一下
其实这种define lid 和 rid 的写法对于动态开点线段树要好写很多,直接把 #define lid (id<<1) #define rid (id<<1)+1 改成 #define lid tree[id].lson #define rid tree[id].rson 就可以了

注意:动态开点和离散化不可以同时用,只可以用一个(实现时只能实现一个)。


代码(附带详细注释):

#include<bits/stdc++.h>
#define lid (id<<1)
#define rid (id<<1)+1
using namespace std;
const int N=100005;

struct Node{
    int l,r;
    int sum;
}tree[N<<2];

int n,Num,num;
int op[N],a[N],b[N];
string type;

inline int read(){
    int x=0,f=1; char ch=getchar();
    while (!isdigit(ch)) { if (ch=='-') f=-1; ch=getchar(); }
    while (isdigit(ch)){ x=x*10+ch-'0'; ch=getchar(); }
    return x*f;
}

void Disc(){
    sort(b+1,b+Num+1);
    Num=unique(b+1,b+Num+1)-b-1;
    for (int i=1;i<=n;i++)
        if (op[i]!=4)
            a[i]=lower_bound(b+1,b+Num+1,a[i])-b;   //完成离散化 
        //b数组存放了值,a[i]存放了原来a[i]离散化后的编号
}

inline void build(int id,int l,int r){      //处理每个点的左右编号 
    tree[id].l=l,tree[id].r=r;
    if (l==r) return;
    int mid=(l+r)>>1;
    build(lid,l,mid);
    build(rid,mid+1,r);
}

inline void modify(int id,int x,int val){       //插入/删除数 x 
    if (tree[id].l==tree[id].r){
        tree[id].sum+=val;
        return;
    }
    int mid=(tree[id].l+tree[id].r)>>1;     //与普通线段树相同 
    if (x<=mid) modify(lid,x,val);
    else modify(rid,x,val);
    tree[id].sum=tree[lid].sum+tree[rid].sum; 
}

inline int query(int id,int x){ //查询 x 的相关信息 
    if (tree[id].l==tree[id].r){    //查找到叶子节点了 
        if (type=="Rank") return 1;     //查找 x 的排名,返回1(见上方第三条规则) 
        if (type=="Pre") return 0;      //查找 x 的前驱,返回0(当前的 x 不算) 
        if (type=="Next") return tree[id].sum+1;    //查找 x 的后继,返回 x 之前的个数+ x 的个数+1 
    }
    int mid=(tree[id].l+tree[id].r)>>1;
    if (x<=mid) return query(lid,x);
    else return tree[lid].sum+query(rid,x);     //如果在右侧,那么加上左侧的个数(左侧的一定比 x 小) 
}

inline int find_kth(int id,int x){      //查询排名为 x 的数 
//思想是不断把 x 减去找到的个数,x=0时返回 
    if (tree[id].l==tree[id].r) return tree[id].l;  //返回找到的数的编号 
    if (x<=tree[lid].sum) return find_kth(lid,x);
    else return find_kth(rid,x-tree[lid].sum);
}

int main(){
    //freopen("Weighted Segment Tree.in","r",stdin);
    //freopen("Weighted Segment Tree.out","w",stdout);
    n=read();
    Num=0;      //Num统计元素个数 
    for (int i=1;i<=n;i++){
        op[i]=read(),a[i]=read();       //离线操作 
        if (op[i]!=4) b[++Num]=a[i];    //b是离散化数组 
    }
    Disc();     //Discretization,离散化 
    build(1,1,Num);
    for (int i=1;i<=n;i++){
        if (op[i]==1) modify(1,a[i],1);     //出现次数+1 
        if (op[i]==2) modify(1,a[i],-1);        //出现次数-1 
        if (op[i]==3) { type="Rank"; printf("%d\n",query(1,a[i])); };
        if (op[i]==4) printf("%d\n",b[find_kth(1,a[i])]);
        if (op[i]==5) { type="Pre"; num=query(1,a[i]); printf("%d\n",b[find_kth(1,num)]); };
        if (op[i]==6) { type="Next"; num=query(1,a[i]); printf("%d\n",b[find_kth(1,num)]); };
        //op=3,5,6的时候,type记录了查询的类型
        //(因为3,5,6操作内容相近,为了代码简洁可以放在一个函数里执行) 
    }
    return 0;
}

这么详细的博客,都看到这里了不点个赞么$QvQ$(小声


我们无法选择过去,但我们可以改变未来。