权值线段树

代码模板

权值线段树的原理与实现:按值域维护元素个数,查询第 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 小。

这就是权值线段树能求第 kk 小的原因。

支持的操作

权值线段树常用来维护一个可重集合,支持:

  1. 插入一个数。
  2. 删除一个数。
  3. 查询某个数的排名。
  4. 查询第 kk 小。
  5. 查询前驱。
  6. 查询后继。

这些操作正好对应普通平衡树模板题。

算法步骤

插入与删除

插入 x:

  1. 从根节点表示的整个值域开始。
  2. 根据 x 落在左半还是右半递归。
  3. 沿途所有节点的 sum 加 1。
  4. 到达叶子 x。

删除 x 同理,只是沿途 sum 减 1。

查询排名

x 的排名是集合中小于 x 的数的个数再加一:

rank(x)=count(<x)+1 rank(x)=count(<x)+1

所以只需要查询值域:

[min_value, x - 1]

中的计数和。

查询第 k 小

从根开始:

  1. 设左子树计数为 left_sum。
  2. 若 k <= left_sum,答案在左子树。
  3. 否则答案在右子树,令 k -= left_sum。
  4. 到叶子时,叶子对应的值就是答案。

查询前驱和后继

前驱是严格小于 x 的最大数:

  1. 先算 cnt = count(<x)。
  2. 前驱就是第 cnt 小。

后继是严格大于 x 的最小数:

  1. 先算 cnt = count(<=x)。
  2. 后继就是第 cnt+1 小。

算法证明

关键不变量:每个节点的 sum 等于它表示的值域区间中,所有数字的出现次数总和。

插入和删除时,只会影响从根到对应叶子的一条路径。沿途节点的值域都包含这个数,所以它们的 sum 应该同步变化;其它节点不包含这个数,所以不变。不变量保持。

查询第 kk 小时,左子树 sum 表示当前区间左半部分有多少个数:

  • 如果 k 不超过左子树数量,答案一定在左边。
  • 如果 k 超过左子树数量,左边所有数都排在答案前面,答案在右边,并且排名变成 k-left_sum。

每次都排除一半值域,直到叶子,得到的值就是第 kk 小。

复杂度分析

设值域大小为 VV。

  • 插入:O(log⁡V)O(\log V)。
  • 删除:O(log⁡V)O(\log V)。
  • 查询排名:O(log⁡V)O(\log V)。
  • 查询第 kk 小:O(log⁡V)O(\log V)。
  • 查询前驱、后继:O(log⁡V)O(\log V)。

如果值域很大但实际出现的数很少,可以使用动态开点,只创建被访问到的节点。

代码实现

C++
cpp
        
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; }
Python

递归重载方法不再需要:add / remove / rank_of / kth_smallest / predecessor / successor 都是模块级函数,内部直接读全局的 root(与 C++ 版一致)。kth / 前驱 / 后继无解时行为与 C++ 相同;换一组数据前先调 init() 清空节点池。

python
        
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。

应用分类详解

权值线段树的本质是“在值域上维护频率”。看到动态插入删除数字,同时还要按大小顺序查询时,就应该想到它。

一、普通平衡树操作

典型模式: 动态维护一个可重集合,支持排名、第 kk 小、前驱、后继。

识别信号: 操作包含 insert、delete、rank、kth、predecessor、successor。

核心建模: 每个值的出现次数是叶子计数,节点维护区间总次数。

二、动态中位数

典型模式: 一边插入数字,一边查询当前中位数。

识别信号: 在线维护第 ⌈n/2⌉\lceil n/2\rceil 小。

核心建模: 每次插入后查询第 kk 小。

三、逆序对与偏序计数

典型模式: 枚举当前数时,需要知道之前有多少数比它大或比它小。

识别信号: “前面大于它的数”“排名统计”“值域计数”。

核心建模: 插入已扫描数字,查询值域区间计数。

四、值域上的区间统计

典型模式: 问当前集合中落在某个值域范围内的数有多少个。

识别信号: 数值范围查询、频率统计、区间桶。

核心建模: 查询 [L,R] 的计数和。

经典例题

1. 普通平衡树

luogu-P3369

权值线段树可以在值域已知或可动态开点时替代平衡树,完成六种基础操作。

2. 中位数

luogu-P1168

不断插入数字并输出中位数。离散化后用权值线段树维护第 kk 小。

3. 逆序对

从左到右扫描数组。当前数 aia_i 的贡献是已插入数中大于 aia_i 的数量。

参考

  • 本书线段树单点修改:data_structure/segment_tree/update_one/index.md
  • 本书树状数组:data_structure/BIT/index.md