专栏文章

权值线段树

RRorre_y
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miql6wnk
此快照首次捕获于
2025/12/04 06:36
3 个月前
此快照最后确认于
2025/12/04 06:36
3 个月前
查看原文

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

权值线段树的基础与运用

1.什么是权值线段树

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

2.权值线段树的原理

这部分内容部分引自某大佬的文章。
比如现在有一个数组
a=[1,1,2,2,2,3,4,5,6,7,8]a=[1,1,2,2,2,3,4,5,6,7,8]
对于每个节点，初始时个数为 00： 1
把所有1插入：
2
类似的，插入所有2：
3
最后：
4
不难看出，权值线段树复杂度为log⁡max⁡a\log \max{a}，其中max⁡a\max{a} 为数组中最大的权值，即数字的最大值。相比于桶排序 max⁡a\max{a} 的复杂度已经有了很大的进步。

3.如何使用权值线段树

因为缺乏模板题，所以借用别的题目粗略讲一下。
题目大意：
您需要动态地维护一个可重集合 MM，并且提供以下操作：
  1. 向 MM 中插入一个数 xx。
  2. 从 MM 中删除一个数 xx（若有多个相同的数，应只删除一个）。
  3. 查询 MM 中有多少个数比 xx 小，并且将得到的答案加一。
  4. 查询如果将 MM 从小到大排列后，排名位于第 xx 位的数。
  5. 查询 MM 中 xx 的前驱（前驱定义为小于 xx，且最大的数）。
  6. 查询 MM 中 xx 的后继（后继定义为大于 xx，且最小的数）。
对于操作 3,5,6，不保证当前可重集中存在数 xx。
分析题目：
使用桶排序必定超时，考虑权值线段树。
先用前缀和预处理。这里不做介绍。
对于操作 11 和 22，只要相应改变该权值对应的数量即可。
对于操作 33，将所有权值小于该值的数量求和即可。
对于操作 44，考虑二分查找，若左子树权值和小于等于排名，那么查找右子树，否则查找左子树。
对于操作 55、66，查找权值前后第一个数量不为 00 的权值即可。

4.代码

"Talk is cheap,show me the code."
代码来自上面那位大佬的文章。
由于该题需要离散化等操作，超出本文讨论范围，这里不细讲。
CPP
#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

鸣谢：

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

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...