权值线段树 学习笔记_权值线段树 入门题

权值线段树

权值线段树是基于线段树的一种数据结构；

线段树维护的是区间信息，比如区间和，区间最大值等等；

而权值线段树维护的是全局的值域信息，每个结点记录是该结点所包含区间的值出现的次数；

权值线段树支持：

1. 查询全局第k小值
2. 查询某个值全局的排名
3. 查询全局某个值的前驱
4. 查询全局某个值的后继

这些操作本来是平衡树的基本操作，但是权值线段树也可以实现，并且代码更加简单；

但是一个很大的劣势是当值域较大（10^9）时，需要离散化，也就是变成了离线算法；

这里主要讲权值线段树的这几个用法，具体实现过程不展开：

以下所有代码都来做于这道题：P3369 【模板】普通平衡树

1、建树：

每道题的建树都不太一样，但是大同小异，记住这个跟普通线段树的区别在于叶子结点记录是这个结点所包含的区间的值出现次数；

void build(int l,int r,int k){
	tr[k].l=l,tr[k].r=r;
	if(l==r) return;
	int d=(l+r)>>1;
	build(l,d,ls);
	build(d+1,r,rs);
}
1
2
3
4
5
6
7

2、插入删除

插入删除和普通线段树一样，当加入某个数时，加 1 ，删除某个数时，加 -1；

void update(int x,int w,int k){//在x点加1 
	if(tr[k].l==tr[k].r){
		tr[k].w+=w;
		return;
	}
	int d=(tr[k].l+tr[k].r)>>1;
	if(x<=d) update(x,w,ls);
	else update(x,w,rs);
	tr[k].w=tr[ls].w+tr[rs].w;
} 
1
2
3
4
5
6
7
8
9
10

3、查询全局第K小值

这里要注意的点就是，当左子树的值大于K时，说明左子树有解，否则递归右子树，但是记得减去左子树的值；

void Xth(int x,int k){//第x小值 
	if(tr[k].l==tr[k].r){
		ans=tr[k].l;
		return;
	}
	if(tr[ls].w>=x) Xth(x,ls);
	else Xth(x-tr[ls].w,rs); 
}
1
2
3
4
5
6
7
8

4、查询某个值x的全局排名

其实就是查找1 – x-1 这个区间和，然后再加 1 ；

void Rank(int x,int k){//x的排名，就是求1-(x-1)的区间和 
	if(tr[k].l>=1&&tr[k].r<=x){
		ans+=tr[k].w;
		return;
	}
	int d=(tr[k].l+tr[k].r)>>1;
	if(1<=d) Rank(x,ls);
	if(x>d) Rank(x,rs);
}
1
2
3
4
5
6
7
8
9

5、查询某个值x的前驱；

这个就比较复杂，其实主要就是二分思想；

这里贴一下代码，主要还是自己理解：

int Findp(int k){//找到这结点k区间的最右边的数 
	if(tr[k].l==tr[k].r) return tr[k].l;
	if(tr[rs].w) return Findp(rs);
	return Findp(ls);
}
int Pre(int x,int k){//x的前驱 
	if(tr[k].r<x){
		if(tr[k].w) return Findp(k);
		return 0;
	} 
	int d=(tr[k].l+tr[k].r)>>1;
	int ans=0;
	if(d<x-1&&tr[rs].w&&(ans=Pre(x,rs))) return ans;
	return Pre(x,ls);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

6、查询某个值x的后继

原理和前驱一样；

int Findn(int k){//找到这结点k区间的最左边的数 
	if(tr[k].l==tr[k].r) return tr[k].l;
	if(tr[ls].w) return Findn(ls);
	return Findn(rs);
}
int Nex(int x,int k){//x的后驱 
	if(tr[k].l>x){
		if(tr[k].w) return Findn(k);
		return 0;
	}
	int d=(tr[k].l+tr[k].r)>>1;
	int ans=0;
	if(x<d&&tr[ls].w&&(ans=Nex(x,ls))) return ans;
	return Nex(x,rs);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

最后贴一下这道题的总代码：

#include<bits/stdc++.h>
#define ll long long
#define pa pair<int,int>
#define ls k<<1
#define rs k<<1|1
#define inf 0x3f3f3f3f
using namespace std;
const int N=100100;
const int M=10000000;
const ll mod=100000000;
struct Nod{
	int opt,x;
}a[N];
int b[N],c[N];
int f1[M*2+100],f2[N];
int n,ans;
struct Node{
	int l,r,w;
}tr[N<<2];
void build(int l,int r,int k){
	tr[k].l=l,tr[k].r=r;
	if(l==r) return;
	int d=(l+r)>>1;
	build(l,d,ls);
	build(d+1,r,rs);
}
void update(int x,int w,int k){//在x点加1 
	if(tr[k].l==tr[k].r){
		tr[k].w+=w;
		return;
	}
	int d=(tr[k].l+tr[k].r)>>1;
	if(x<=d) update(x,w,ls);
	else update(x,w,rs);
	tr[k].w=tr[ls].w+tr[rs].w;
} 
void Xth(int x,int k){//第x小值 
	if(tr[k].l==tr[k].r){
		ans=tr[k].l;
		return;
	}
	if(tr[ls].w>=x) Xth(x,ls);
	else Xth(x-tr[ls].w,rs); 
}
void Rank(int x,int k){//x的排名，就是求1-(x-1)的区间和 
	if(tr[k].l>=1&&tr[k].r<=x){
		ans+=tr[k].w;
		return;
	}
	int d=(tr[k].l+tr[k].r)>>1;
	if(1<=d) Rank(x,ls);
	if(x>d) Rank(x,rs);
}
int Findp(int k){//找到这结点k区间的最右边的数 
	if(tr[k].l==tr[k].r) return tr[k].l;
	if(tr[rs].w) return Findp(rs);
	return Findp(ls);
}
int Pre(int x,int k){//x的前驱 
	if(tr[k].r<x){
		if(tr[k].w) return Findp(k);
		return 0;
	} 
	int d=(tr[k].l+tr[k].r)>>1;
	int ans=0;
	if(d<x-1&&tr[rs].w&&(ans=Pre(x,rs))) return ans;
	return Pre(x,ls);
}
int Findn(int k){//找到这结点k区间的最左边的数 
	if(tr[k].l==tr[k].r) return tr[k].l;
	if(tr[ls].w) return Findn(ls);
	return Findn(rs);
}
int Nex(int x,int k){//x的后驱 
	if(tr[k].l>x){
		if(tr[k].w) return Findn(k);
		return 0;
	}
	int d=(tr[k].l+tr[k].r)>>1;
	int ans=0;
	if(x<d&&tr[ls].w&&(ans=Nex(x,ls))) return ans;
	return Nex(x,rs);
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    int cnt=0;
    for(int i=1;i<=n;i++){
    	cin>>a[i].opt>>a[i].x;
    	if(a[i].opt==1||a[i].opt==3||a[i].opt==5||a[i].opt==6){
    		b[++cnt]=a[i].x;
    		c[cnt]=b[cnt];
		}
	}
	sort(b+1,b+1+cnt);
	int tot=cnt;
	cnt=unique(b+1,b+cnt+1)-b-1;
	for(int i=1;i<=tot;i++){//离散化 
		int po=lower_bound(b+1,b+cnt+1,c[i])-b;
		f1[c[i]+M]=po;
		f2[po]=c[i];
	}
	build(1,N,1);
	for(int i=1;i<=n;i++){
		if(a[i].opt==1) update(f1[a[i].x+M],1,1);
		else if(a[i].opt==2) update(f1[a[i].x+M],-1,1);
		else if(a[i].opt==3){
			ans=0;
			Rank(f1[a[i].x+M]-1,1);
			cout<<ans+1<<endl;
		}
		else if(a[i].opt==4){
			ans=0;
			Xth(a[i].x,1);
			cout<<f2[ans]<<endl;
		}
		else if(a[i].opt==5){
			cout<<f2[Pre(f1[a[i].x+M],1)]<<endl;
		}
		else{
			cout<<f2[Nex(f1[a[i].x+M],1)]<<endl;
		}
	}
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125