权值线段树
代码模板权值线段树的原理与实现:按值域维护元素个数,查询第 K 小与排名。
一句话算法
权值线段树不是维护下标区间,而是维护值域区间;每个叶子表示一个数出现了多少次。
问题模型
普通线段树通常维护数组下标:
index: 1 2 3 4 5 ...
value: a1 a2 a3 ...
权值线段树维护的是数值本身:
value: 1 2 3 4 5 ...
count: 出现次数
如果当前集合是:
3, 3, 5, 8
那么值域上的计数是:
count[3] = 2
count[5] = 1
count[8] = 1
线段树每个节点维护一段值域中出现的总次数。
核心直觉
把每个数字看成一个桶。插入数字 x,就是让 x 这个桶的计数加一;删除数字 x,就是让计数减一。
权值线段树把很多桶按值域区间分组:
[1, 8]
├── [1, 4]
└── [5, 8]
如果左子树一共有 cnt 个数:
- 第
k小在左边,当k <= cnt。 - 第
k小在右边,当k > cnt,并且要找右边的第k-cnt小。
这就是权值线段树能求第
支持的操作
权值线段树常用来维护一个可重集合,支持:
- 插入一个数。
- 删除一个数。
- 查询某个数的排名。
- 查询第
小。 - 查询前驱。
- 查询后继。
这些操作正好对应普通平衡树模板题。
算法步骤
插入与删除
插入 x:
- 从根节点表示的整个值域开始。
- 根据
x落在左半还是右半递归。 - 沿途所有节点的
sum加1。 - 到达叶子
x。
删除 x 同理,只是沿途 sum 减 1。
查询排名
x 的排名是集合中小于 x 的数的个数再加一:
所以只需要查询值域:
[min_value, x - 1]
中的计数和。
查询第 k 小
从根开始:
- 设左子树计数为
left_sum。 - 若
k <= left_sum,答案在左子树。 - 否则答案在右子树,令
k -= left_sum。 - 到叶子时,叶子对应的值就是答案。
查询前驱和后继
前驱是严格小于 x 的最大数:
- 先算
cnt = count(<x)。 - 前驱就是第
cnt小。
后继是严格大于 x 的最小数:
- 先算
cnt = count(<=x)。 - 后继就是第
cnt+1小。
算法证明
关键不变量:每个节点的 sum 等于它表示的值域区间中,所有数字的出现次数总和。
插入和删除时,只会影响从根到对应叶子的一条路径。沿途节点的值域都包含这个数,所以它们的 sum 应该同步变化;其它节点不包含这个数,所以不变。不变量保持。
查询第 sum 表示当前区间左半部分有多少个数:
- 如果
k不超过左子树数量,答案一定在左边。 - 如果
k超过左子树数量,左边所有数都排在答案前面,答案在右边,并且排名变成k-left_sum。
每次都排除一半值域,直到叶子,得到的值就是第
复杂度分析
设值域大小为
- 插入:
。 - 删除:
。 - 查询排名:
。 - 查询第
小: 。 - 查询前驱、后继:
。
如果值域很大但实际出现的数很少,可以使用动态开点,只创建被访问到的节点。
代码实现
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
#include <bits/stdc++.h>
using namespace std;
// 权值线段树(动态开点):按值域统计每个数出现的次数,
// 支持插入、删除、排名、第 k 小、前驱与后继。
const int maxn = 2000000 + 5; // 节点池大小:按操作次数 * log(值域) 估
const int MINV = -10000000; // 值域下界
const int MAXV = 10000000; // 值域上界
int lc[maxn]; // lc[p]:p 的左儿子下标,0 表示空
int rc[maxn]; // rc[p]:p 的右儿子下标,0 表示空
int cnt[maxn]; // cnt[p]:p 管辖区间内的元素个数
int root = 0; // 根节点下标,0 表示空树
int tot = 0; // 已分配的节点数,0 号节点固定为空节点
// 新建一个空节点并返回它的下标
int new_node() {
++tot;
lc[tot] = rc[tot] = cnt[tot] = 0;
return tot;
}
// 在值域区间 [l, r] 的节点 p 上把 pos 的个数增加 delta
void update(int &p, int l, int r, int pos, int delta) {
if (!p) p = new_node(); // 走到空节点就开一个,这是“动态开点”
cnt[p] += delta;
if (l == r) return;
int mid = l + ((r - l) >> 1); // 防溢出的中点写法
if (pos <= mid) update(lc[p], l, mid, pos, delta);
else update(rc[p], mid + 1, r, pos, delta);
}
// 区间计数:值域 [ql, qr] 内一共有多少个数
int query(int p, int l, int r, int ql, int qr) {
if (!p || qr < l || r < ql) return 0; // 空节点整段都是 0
if (ql <= l && r <= qr) return cnt[p];
int mid = l + ((r - l) >> 1);
int answer = query(lc[p], l, mid, ql, qr);
answer += query(rc[p], mid + 1, r, ql, qr);
return answer;
}
// 小于 x 的元素个数 = 值域 [MINV, x-1] 的计数
int count_less(int x) {
if (x <= MINV) return 0;
return query(root, MINV, MAXV, MINV, x - 1);
}
// 第 k 小:看左儿子的个数够不够,够就往左走,否则往右并扣掉左半段
int kth(int p, int l, int r, int k) {
if (l == r) return l;
int mid = l + ((r - l) >> 1);
if (k <= cnt[lc[p]]) return kth(lc[p], l, mid, k);
return kth(rc[p], mid + 1, r, k - cnt[lc[p]]);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
while (n--) {
int op, x;
cin >> op >> x;
if (op == 1) {
update(root, MINV, MAXV, x, 1); // 插入
} else if (op == 2) {
update(root, MINV, MAXV, x, -1); // 删除
} else if (op == 3) {
cout << count_less(x) + 1 << '\n'; // 排名
} else if (op == 4) {
cout << kth(root, MINV, MAXV, x) << '\n'; // 第 k 小
} else if (op == 5) {
cout << kth(root, MINV, MAXV, count_less(x)) << '\n'; // 前驱
} else {
// 后继:大于 x 的最小数 = 第 (≤x 的个数 + 1) 小
int leq = count_less(x + 1);
cout << kth(root, MINV, MAXV, leq + 1) << '\n';
}
}
return 0;
}
递归重载方法不再需要:add / remove / rank_of / kth_smallest / predecessor / successor 都是模块级函数,内部直接读全局的 root(与 C++ 版一致)。kth / 前驱 / 后继无解时行为与 C++ 相同;换一组数据前先调 init() 清空节点池。
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
# 权值线段树(动态开点):按值域统计每个数出现的次数,
# 支持插入、删除、排名、第 k 小、前驱与后继。
# 与 C++ 版一一对应:全局列表 lc / rc / cnt(下标即指针)+ 独立函数。
# 节点 0 是空哨兵:lc[0] = rc[0] = cnt[0] = 0,所以“p 为 0”表示这棵子树全空。
# 下标池用 append 动态增长,不必像 C++ 那样先估一个 MAXNODE。
MINV: int = -10000000 # 值域下界
MAXV: int = 10000000 # 值域上界
lc: list[int] = [0] # lc[p]:p 的左儿子下标,0 表示空
rc: list[int] = [0] # rc[p]:p 的右儿子下标,0 表示空
cnt: list[int] = [0] # cnt[p]:p 管辖区间内的元素个数
root: int = 0 # 根节点下标,0 表示空树
tot: int = 0 # 已分配的节点数,0 号节点固定为空节点
def init() -> None:
"""清空整棵权值线段树,换一组数据前必须先调用。"""
global lc, rc, cnt, root, tot
lc = [0]
rc = [0]
cnt = [0]
root = 0
tot = 0
def new_node() -> int:
"""新建一个空节点并返回它的下标。"""
global tot
tot += 1
lc.append(0)
rc.append(0)
cnt.append(0)
return tot
def update(p: int, l: int, r: int, pos: int, delta: int) -> int:
"""在值域区间 [l, r] 上把 pos 的个数增加 delta,返回该子树(可能新建)的根。"""
if p == 0:
p = new_node() # 走到空节点就开一个,这是“动态开点”
cnt[p] += delta
if l == r:
return p
mid = l + ((r - l) >> 1) # 防溢出的中点写法
if pos <= mid:
lc[p] = update(lc[p], l, mid, pos, delta)
else:
rc[p] = update(rc[p], mid + 1, r, pos, delta)
return p
def query(p: int, l: int, r: int, ql: int, qr: int) -> int:
"""值域 [ql, qr] 内一共有多少个数;p 为 0 时整段都是 0。"""
if p == 0 or qr < l or r < ql:
return 0
if ql <= l and r <= qr:
return cnt[p]
mid = l + ((r - l) >> 1)
answer = query(lc[p], l, mid, ql, qr)
answer += query(rc[p], mid + 1, r, ql, qr)
return answer
def count_less(x: int) -> int:
"""小于 x 的元素个数 = 值域 [MINV, x-1] 的计数。"""
if x <= MINV:
return 0
return query(root, MINV, MAXV, MINV, x - 1)
def kth(p: int, l: int, r: int, k: int) -> int:
"""第 k 小(k 从 1 开始):左儿子够就往左,否则往右并扣掉左半段。"""
if l == r:
return l
mid = l + ((r - l) >> 1)
if k <= cnt[lc[p]]:
return kth(lc[p], l, mid, k)
return kth(rc[p], mid + 1, r, k - cnt[lc[p]])
def add(x: int) -> None:
"""插入一个 x(等价于 C++ 里的 update(root, MINV, MAXV, x, 1))。"""
global root
root = update(root, MINV, MAXV, x, 1)
def remove(x: int) -> None:
"""删除一个 x,要求 x 当前存在。"""
global root
root = update(root, MINV, MAXV, x, -1)
def rank_of(x: int) -> int:
"""x 的排名(比 x 小的个数 + 1)。"""
return count_less(x) + 1
def kth_smallest(k: int) -> int:
"""第 k 小。"""
return kth(root, MINV, MAXV, k)
def predecessor(x: int) -> int:
"""小于 x 的最大元素。"""
return kth(root, MINV, MAXV, count_less(x))
def successor(x: int) -> int:
"""大于 x 的最小元素:第 (≤x 的个数 + 1) 小。"""
return kth(root, MINV, MAXV, count_less(x + 1) + 1)
测试用例
输入:
10
1 5
1 3
1 7
3 5
4 2
5 5
6 5
2 5
4 2
3 7
输出:
2
5
3
7
7
2
过程:
- 插入
5,3,7后,集合为{3,5,7}。 5的排名是2。- 第
2小是5。 5的前驱是3,后继是7。- 删除
5后,集合为{3,7},第2小是7。
应用分类详解
权值线段树的本质是“在值域上维护频率”。看到动态插入删除数字,同时还要按大小顺序查询时,就应该想到它。
一、普通平衡树操作
典型模式: 动态维护一个可重集合,支持排名、第
识别信号: 操作包含 insert、delete、rank、kth、predecessor、successor。
核心建模: 每个值的出现次数是叶子计数,节点维护区间总次数。
二、动态中位数
典型模式: 一边插入数字,一边查询当前中位数。
识别信号: 在线维护第
核心建模: 每次插入后查询第
三、逆序对与偏序计数
典型模式: 枚举当前数时,需要知道之前有多少数比它大或比它小。
识别信号: “前面大于它的数”“排名统计”“值域计数”。
核心建模: 插入已扫描数字,查询值域区间计数。
四、值域上的区间统计
典型模式: 问当前集合中落在某个值域范围内的数有多少个。
识别信号: 数值范围查询、频率统计、区间桶。
核心建模: 查询 [L,R] 的计数和。
经典例题
1. 普通平衡树
权值线段树可以在值域已知或可动态开点时替代平衡树,完成六种基础操作。
2. 中位数
不断插入数字并输出中位数。离散化后用权值线段树维护第
3. 逆序对
从左到右扫描数组。当前数
参考
- 本书线段树单点修改:
data_structure/segment_tree/update_one/index.md - 本书树状数组:
data_structure/BIT/index.md