第 116 章 平衡树与有序集合¶
配套例题：BISHI5 【模板】多重集合操作、BISHI129 区间增量与区间小于计数 来源：S4
模板.docx/「树 → 二叉排序树（有 splay 就差不多了）」「树 → Splay（三个模板）」（sources/03-pascal-template/模板.md第 46、48 行的清单，以及第 1008 行「Splay（区间翻转版）」、第 1168 行「Splay（常用版）」、第 1470 行「Splay（完全版）」三份源码） 前置：34-集合与多重集合、39-树状数组与线段树、35-优先队列与堆
116.0 这一章为什么存在¶
S4 模板.docx 的目录里，「树」这一节有两个条目值得注意：
第一条的括号是原文照抄——作者连 BST 的代码都没写，理由是「有 Splay 就够了」。 第二条则给了三份完整实现（区间翻转版 / 常用版 / 完全版）， 是整份模板文档里代码量最大的单一算法。这说明什么？
在 C++/Pascal 的竞赛生态里，平衡树是「必须自带的重武器」。 它一个人干了
set、multiset、map、可排序序列、区间翻转五件事。
而牛客题单里没有一道平衡树题。原因是双重的：
| 原因 | 说明 |
|---|---|
| 笔试题单不考手写平衡树 | 太长（Splay 常用版 200+ 行），不适合限时笔试 |
| Python 根本不该写平衡树 | 常数是 C++ 的 30–50 倍，\(n=10^5\) 就能把 10 秒吃光 |
| 有序集合的需求被「值域数据结构」顶掉了 | BISHI4/BISHI5 把值域限死在 \(10^6\)，这是出题人的明示 |
所以这一章的定位很特殊：
| 目标 | 说明 |
|---|---|
| 补上 S4 的知识缺口 | BST 的插入/查询/删除与退化、Splay 的原理与均摊分析 |
| 但明确劝退手写实现 | 只讲原理，不给完整 Splay —— 因为 Python 里写了也用不上 |
| 本章真正的重点：四套替代方案 | 值域位图 / 树状数组倍增 / 堆 + 懒删除 / Counter 离线 |
| 给一张决策表 | 拿到「有序集合需求」时按表选武器 |
| 明确禁用第三方库 | 判题机没有 sortedcontainers |
⚠️ 先说最重要的一件事： 牛客判题机没有安装
sortedcontainers（也没有numpy）。from sortedcontainers import SortedList提交上去就是ModuleNotFoundError， 本地测得再好也没用。见 C-Python竞赛避坑清单。 本章所有代码只依赖标准库。
先给结论：
Python 选手应该把「平衡树」这个词从工具箱里划掉， 换成「值域位图 + 树状数组倍增」这两件。 前者 \(O(1)\) 且全在 C 层，后者 \(O(\log V)\) 但能多做「第 \(k\) 小」和「区间计数」。 这两件覆盖了 S4 那份 Splay API 清单里的全部 8 个操作。
116.1 二叉排序树（BST）¶
BST（binary search tree，二叉排序树，也叫二叉搜索树）的定义： 每个节点的左子树所有键 \(<\) 自己 \(<\) 右子树所有键。 于是中序遍历得到升序序列，这是 BST 的全部性质来源。
| 操作 | 做法 | 复杂度（树高 \(h\)） |
|---|---|---|
| 查询 \(x\) | 从根比较，小往左、大往右 | \(O(h)\) |
| 插入 \(x\) | 一路走到空位挂上去 | \(O(h)\) |
| 前驱 / 后继 | 走到 \(x\) 后取「左子树最大 / 右子树最小」，或路径上的转折点 | \(O(h)\) |
| 第 \(k\) 小 | 每个节点额外维护 size，按 size 决定往哪边走 |
\(O(h)\) |
| 删除 \(x\) | 分三种情况，见下 | \(O(h)\) |
删除是唯一有技术含量的操作，三种情况：
| 情况 | 做法 |
|---|---|
| 叶子 | 直接摘掉 |
| 只有一个孩子 | 用那个孩子顶替自己 |
| 有两个孩子 | 找右子树的最小值（即后继）覆盖自己的键，再去删那个后继节点 |
第三种情况的关键：后继节点一定没有左孩子（否则它就不是最小）， 所以递归下去必然落到前两种情况，不会无限套娃。
# [片段]
class BST:
"""二叉排序树（数组实现，全部非递归）。仅作教学演示 —— 竞赛里不要用。
节点编号 1..cnt，0 表示空。key/lc/rc 三个平行数组。
⚠️ 没有任何平衡措施：有序插入会退化成链，所有操作变 O(n)。
"""
def __init__(self, cap):
self.key = [0] * (cap + 1)
self.lc = [0] * (cap + 1)
self.rc = [0] * (cap + 1)
self.cnt = 0
self.root = 0
def insert(self, x):
self.cnt += 1 # 节点编号从 1 开始发，0 号永远留给「空」
i = self.cnt
self.key[i] = x
if not self.root:
self.root = i # 空树：新节点直接当根
return
p = self.root
while True: # 一路下滑到空位
if x < self.key[p]:
if self.lc[p]:
p = self.lc[p] # 左边有人，继续往下
else:
self.lc[p] = i # 左边是空位，挂上去即可
return
else: # >= 走右边 —— 于是相等元素也能共存（多重集合）
if self.rc[p]:
p = self.rc[p]
else:
self.rc[p] = i
return
def find(self, x):
p = self.root
while p: # p 变成 0 表示走到空位，说明 x 不在树里
if self.key[p] == x:
return True
p = self.lc[p] if x < self.key[p] else self.rc[p] # 小往左、大往右
return False
def erase(self, x):
"""删除一个值为 x 的节点，返回是否删掉。"""
par = 0 # 0 表示「p 就是根，没有父亲」
p = self.root
while p and self.key[p] != x: # 同时记住父亲，省掉递归
par = p
p = self.lc[p] if x < self.key[p] else self.rc[p]
if not p:
return False # 一路走到空位都没找到
if self.lc[p] and self.rc[p]: # ★ 两个孩子：用「右子树最小值」顶替
sp = p # sp 是后继的父亲，初值就是 p 自己
s = self.rc[p]
while self.lc[s]: # 在右子树里一直往左走，尽头即最小值
sp = s
s = self.lc[s]
self.key[p] = self.key[s] # 只搬键值，不改动树的连接关系
p, par = s, sp # 转而去删 s（它必无左孩子）
child = self.lc[p] or self.rc[p] # 此时 p 至多一个孩子
# 两个都为 0 时 child 也是 0，叶子情形自动包含在内
if par == 0:
self.root = child # 删的是根，让孩子上位
elif self.lc[par] == p:
self.lc[par] = child # 要认准 p 挂在父亲哪一侧，接错会丢掉整棵子树
else:
self.rc[par] = child
return True
def inorder(self):
"""中序遍历 = 升序序列。迭代版，不会爆栈。"""
res = []
stk = [] # 显式栈代替递归，树退化成链也不会爆 C 栈
p = self.root
while stk or p: # 栈空且 p 为 0 才算走完
while p:
stk.append(p) # 一路向左，沿途全部压栈
p = self.lc[p]
p = stk.pop() # 左边到底了，弹出的就是当前最小的未访问点
res.append(self.key[p])
p = self.rc[p] # 转向右子树，重复同样的过程
return res
退化问题¶
BST 的所有复杂度都写作 \(O(h)\)，而 \(h\) 完全由插入顺序决定：
| 插入顺序 | 树高 \(h\) | 单次操作 |
|---|---|---|
| 随机 | \(O(\log n)\)（期望 \(\approx 1.39\log_2 n\)） | ✅ |
| 升序 / 降序 | \(n\)（退化成链表） | ❌ \(O(n)\) |
| 先小后大再中间（对抗数据） | \(n\) | ❌ |
⚠️ 「有序插入」不是罕见情形，而是最常见情形。 题目给的数组本来就有序、或者你先排了一次序再插入—— 这两种写法都会把 BST 变成一条链，\(n = 10^5\) 时单次操作 \(10^5\)， 总量 \(10^{10}\)，比暴力还慢。
所以裸 BST 在竞赛里没有任何使用价值。 它的意义只是「理解平衡树在平衡什么」。
修复退化的三条路线：
| 路线 | 代表 | 保证 |
|---|---|---|
| 旋转维持严格平衡 | AVL、红黑树 | 最坏 \(O(\log n)\) |
| 随机化 | Treap、跳表 | 期望 \(O(\log n)\) |
| 均摊：不保证单次，只保证总量 | Splay | 均摊 \(O(\log n)\) |
S4 选的是第三条。
116.2 Splay 伸展树：原理与均摊分析¶
S4 给的三份模板对应三种用途：
| 模板名（S4 原文） | 用途 | 额外字段 |
|---|---|---|
| Splay（区间翻转版） | 把序列存在平衡树里，支持区间翻转 | rev 懒标记 |
| Splay（常用版） | 有序集合：插入/删除/前驱/后继/第 \(k\) 小/排名 | key, size, fa, son[2] |
| Splay（完全版） | 常用版 + 区间加 + 区间删除 | 再加 num（重数）、Add 懒标记 |
核心思想：访问过的节点转到根¶
Splay 只有一个动作：Splay(x, To)——把节点 \(x\) 旋转到 To 的儿子位置
（To = 0 就是旋到根）。每次访问任何节点之后，都把它 splay 到根。
S4「常用版」的 API 清单（原文注释）把这件事写得很清楚：
int find(int key) // 返回值为key的节点 若无返回0 若有将其转移到根处
int prev() // 返回比根值小的最大值 ... 并将其转移到根处
int succ() // 返回比根值大的最小值 ... 并将其转移到根处
void Insert(int key)// 插入key 并且将该节点转移到根处
void Delete(int key)// 删除值为key的节点 ... x的前驱移动到根处
int GetPth(int p) // 获得第p小的节点 并将其转移到根处
int GetRank(int key)// 获得值<=key的节点个数 并将其转移到根处
七个操作，七次「转移到根处」——这不是巧合，是 Splay 的全部机制。
三种旋转¶
设 \(x\) 的父亲是 \(y\)、祖父是 \(z\)：
| 情形 | 名字 | 做法 |
|---|---|---|
| \(y\) 就是根 | zig（单旋） | 直接把 \(x\) 转上来 |
| \(x, y\) 同侧（都是左儿子，或都是右儿子） | zig-zig（一字型） | 先转 \(y\)，再转 \(x\)（顺序不能反！） |
| \(x, y\) 异侧 | zig-zag（之字型） | 转 \(x\) 两次 |
S4 的 Splay 函数正是这个三分支结构（模板.md 第 1246 行起）：
void Splay(int x, int To) {
while (T[x].fa != To) {
if (T[T[x].fa].fa == To) // zig：父亲就是终点
Rotate(x, T[T[x].fa].son[0] == x);
else { int y = T[x].fa, z = T[y].fa; ... } // zig-zig / zig-zag
}
}
⚠️ zig-zig 必须「先转父亲，再转自己」。 如果图省事写成「转 \(x\) 两次」，Splay 就退化成朴素的「移到根」策略， 均摊复杂度从 \(O(\log n)\) 掉到 \(O(n)\)——链状树上插入 \(1..n\) 再依次访问， 每次都是 \(O(n)\)。这是 Splay 唯一但也是最致命的实现坑。 zig-zig 的「先父后子」能把长链对折，这才是压缩树高的机制。
均摊 \(O(\log n)\) 的证明思路（势能法）¶
定义节点 \(x\) 的秩 \(r(x) = \log_2 \operatorname{size}(x)\)， 整棵树的势能 \(\Phi = \sum_x r(x)\)。
Access Lemma：一次 Splay(x) 的均摊代价
\(\le 3\big(r(\text{root}) - r(x)\big) + 1 = O(\log n)\)。
证明的骨架是：每个 zig-zig / zig-zag 步骤的「实际代价 + 势能变化」都可以被 \(3(r'(x) - r(x))\) 界住（\(r'\) 是旋转后的秩），沿路径求和后中间项全部消掉， 只剩首尾两项 \(3(r(\text{root}) - r(x))\)。
| 结论 | 含义 |
|---|---|
| 单次操作可以是 \(O(n)\) | Splay 不保证任何单次操作的复杂度 |
| \(m\) 次操作总量 \(O((n+m)\log n)\) | 只保证总量 |
| 有「自适应」红利 | 频繁访问的元素会待在根附近，实际比 \(\log n\) 更快 |
「均摊」在竞赛里意味着什么： 只要题目要的是「\(m\) 次操作的总时间」，均摊和最坏一样好用； 但如果题目要求「每次操作都不超过某个时限」（在线交互题），均摊就不够了。 竞赛里几乎全是前者，所以 Splay 完全够用——在 C++ 里。
为什么本章不给 Python 的完整 Splay¶
| 项 | C++ Splay | Python Splay |
|---|---|---|
| 单次旋转 | ~10 条指令 | ~30 次 list 索引 + 边界判断 |
| \(n = q = 10^5\)，每次操作约 \(2\log n\) 次旋转 | 0.05 s | \(10^5 \times 34 \times 30 = 10^8\) 次 Python 层操作 ≈ 60–100 s |
| 代码量 | 150–250 行 | 同等，且调试难度极高 |
| 递归深度 | 迭代实现无问题 | 同 |
这就是本章「只讲原理」的理由： 一个在实用规模上永远打不过
list暴力的数据结构，写它是纯粹的浪费。 理解它，然后用下面四套替代方案。
Splay 唯一无法替代的场景¶
诚实起见要说清楚：有一件事替代方案做不到。
| 需求 | 替代方案 | 说明 |
|---|---|---|
| 有序集合（插入/删除/前驱/后继/第 \(k\) 小/排名） | ✅ 值域位图 / 树状数组 | 全部覆盖 |
| 可排序序列 + 区间翻转 / 区间移动（「文艺平衡树」） | ❌ 没有替代品 | 这是 S4「区间翻转版」的用途 |
| 动态加边删边的树（LCT） | ❌ | Python 完全不现实 |
遇到「区间翻转 + 区间查询」的题，Python 选手的处理是： 1. 先看 \(n\) 有多小——\(n \le 2\times10^3\) 时直接
list切片翻转（a[l:r] = a[l:r][::-1]， 切片翻转是 C 层操作，\(2\times10^3\) 次 \(\times\) \(2\times10^3\) 长度 = \(4\times10^6\) 次 C 层拷贝，很快）； 2. 再看是否只需最终序列——是则离线倒推； 3. 都不行 → 这道题不是给 Python 的。
116.3 替代方案一：两级值域位图（首选）¶
这是 BISHI4 / BISHI5 的实际最优解，也是本教程最推荐的有序集合实现。
完整模板 ValueSet / ValueMultiset 在
34-集合与多重集合，这里只讲为什么它能赢。
结构¶
把值域 \([0, V]\) 切成每块 BITS = 1024 个值：
| 层 | 存什么 | 大小 |
|---|---|---|
blk[b] |
一个 1024 位的 Python 大整数，第 \(r\) 位 = 值 \(b\cdot1024+r\) 是否存在 | \(V/1024\) 个 |
summ |
一个 \((V/1024)\) 位的大整数，第 \(b\) 位 = 第 \(b\) 块是否非空 | 1 个 |
\(V = 2\times10^6\) 时块数 1954，summ 本身也只是一个 1954 位整数——
依然是一次大整数运算就能扫完。
为什么快：所有循环都消失了¶
| 操作 | 表达式 | 代价 |
|---|---|---|
| 插入 | blk[b] |= 1 << r; summ |= 1 << b |
2 次大整数或 |
| 删除 | blk[b] &= ~(1 << r) |
1 次 |
| 存在性 | (blk[b] >> r) & 1 |
1 次 |
| 前驱 | 块内 blk[b] & ((1<<r)-1) → 取最高位；块内空则去 summ & ((1<<b)-1) 找左边最近的非空块 |
2–4 次 |
| 后继 | 块内 blk[b] >> (r+1) → 取 lowbit；块内空则 summ >> (b+1) |
2–4 次 |
一个 1024 位的大整数只占 16 个 64 位机器字，
一次大整数 &/|/>>/bit_length() 比一次 Python 层循环迭代还便宜。
三条要背下来的位运算恒等式¶
| 目标 | 表达式 |
|---|---|
| 最高位的 1 的位置 | v.bit_length() - 1 |
| 最低位的 1（lowbit） | v & -v |
| 最低位的 1 的位置 | (v & -v).bit_length() - 1 |
| 保留低于第 \(r\) 位 | v & ((1 << r) - 1) （找前驱用） |
| 保留高于第 \(r\) 位 | v >> (r + 1) （找后继用） |
⚠️ 不能用
int.bit_count()——那是 Python 3.10 才有的， 牛客是 3.9。要数 1 的个数只能bin(v).count("1")（也在 C 层，同样快）。
多重集合：位图管有序性，dict 管重数¶
# [片段]
# 有序多重集合 = 位图（有序性，O(1)）+ 计数字典（重数，O(1)）
cnt = {} # 值 -> 出现次数（只存 > 0 的）
blk = [0] * NBLK # 位图：该值是否出现过
summ = 0 # 哪些块非空
total = 0 # 含重复的总个数
# 约定：值 x 落在第 b = x // BITS 块的第 r = x % BITS 位上
# 插入：只有「计数从 0 变 1」才需要点亮位图
c = cnt.get(x, 0)
cnt[x] = c + 1
total += 1
if c == 0:
blk[b] |= 1 << r # 块内点亮第 r 位
summ |= 1 << b # 汇总层记下「第 b 块非空」
# 删除：只有「计数从 1 掉到 0」才需要熄灭位图
c = cnt.get(x, 0)
if c: # c 为 0 说明元素不存在，静默忽略
total -= 1
if c == 1:
del cnt[x] # 计数归零就从字典里删掉，省内存
v = blk[b] & ~(1 << r) # 取反再与，等价于「把第 r 位清成 0」
blk[b] = v
if v == 0: # 整块空了，从 summary 摘掉
summ &= ~(1 << b) # 不摘的话找前驱会跳进空块，白跑一趟
else:
cnt[x] = c - 1 # 还有重复，位图保持点亮
「位图与计数分离」是这个模板的精髓： 有序性完全交给位图（\(O(1)\)、C 层），重数完全交给哈希表（\(O(1)\)）， 两者互不干扰。对比 Splay 要在每个节点上维护
num字段（S4「完全版」就多了这个）， 这里一个dict就搞定。
局限¶
| 局限 | 说明 | 破解 |
|---|---|---|
| 值域必须小 | \(V \le 10^7\)（\(10^7\) bit = 1.25 MB） | 离散化（但要能离线） |
| 值域必须已知上界 | 要先开数组 | 在线且值域未知 → 换方案 |
| 不擅长「第 \(k\) 小」 | 要遍历 summ 的位，\(O(V/w)\) |
需要第 \(k\) 小 → 用树状数组 |
| 不能做「区间计数」 | 位图数 1 是 \(O(V/w)\) | 同上 |
判断口诀： 只要前驱 / 后继 / 存在性 → 值域位图，无脑选它。 要第 \(k\) 小 / 区间计数 → 树状数组。
116.4 替代方案二：树状数组上倍增求第 \(k\) 小¶
在值域上开一棵计数型树状数组：tree 维护「值 \(\le x\) 的元素个数」。
| 操作 | 做法 | 复杂度 |
|---|---|---|
| 插入 / 删除 | 值域下标处 \(\pm1\) | \(O(\log V)\) |
| \(\le x\) 的个数（排名） | 前缀和 | \(O(\log V)\) |
| 第 \(k\) 小 | 树状数组上倍增 | \(O(\log V)\) |
| 前驱 | kth(count_less(x)) |
\(O(\log V)\) |
| 后继 | kth(count_le(x) + 1) |
\(O(\log V)\) |
关键在 kth 的写法。完整模板见
39-树状数组与线段树 · 39.4：
# [片段]
def kth(tree, n, k):
"""计数型树状数组上找第 k 小（k 从 1 开始），O(log V)。
原理：树状数组的节点 i 恰好统计了区间 (i - lowbit(i), i]，
所以从最高位开始试探「能不能往右跳 2^j 步」，就是在树上从根往下走。
★ 千万不要写成「二分答案 + 每次查前缀和」—— 那是 O(log^2 V)。
"""
pos = 0 # 已确认「前 pos 个值域位置」装不下 k 个元素
for j in range(n.bit_length(), -1, -1): # 从最高位试到第 0 位，等于在树上自顶向下走
nxt = pos + (1 << j) # 试探：再往右跳 2^j 步行不行
if nxt <= n and tree[nxt] < k: # 不越界、且跳过去仍不足 k -> 这一跳可以走
pos = nxt
k -= tree[pos] # 扣掉这一段已经装下的元素个数
return pos + 1 # pos+1 就是答案（值域下标）
# 循环结束时 pos 是「前缀和仍 < k」的最大下标
\(O(\log V)\) vs \(O(\log^2 V)\) 在 Python 里是「能过」和「TLE」的区别： \(n = 10^5\)、\(V = 2\times10^6\)（\(\log V = 21\)）时 前者是 \(2.1\times10^6\) 次迭代（约 0.3 s），后者是 \(4.4\times10^7\) 次（约 6 s）。
与位图的量化对比¶
| 值域位图 | 树状数组 + 倍增 | |
|---|---|---|
| 前驱 / 后继 | \(O(1)\)，2–4 次 C 层大整数运算 | \(O(\log V)\)，约 \(2\times21 = 42\) 次 Python 层迭代 |
| 第 \(k\) 小 | ❌ \(O(V/w)\) | ✅ \(O(\log V)\) |
| 区间计数（值在 \([l,r]\) 的个数） | ❌ | ✅ \(O(\log V)\) |
| 支持负权 / 带权计数 | ❌ 只能存在性 | ✅ |
| \(n = 10^5\) 次操作的总迭代数 | \(\approx 3\times10^5\) 次 C 层运算 | \(\approx 2\times10^6\) 次 Python 层迭代 |
| \(n = 10^5\) 实测 | 0.1–0.2 s | 0.3–0.5 s |
| \(n = 10^6\) | ✅ 1–2 s | ⚠️ 4–6 s |
两者不是竞争关系，是分工关系： BISHI5 只要前驱后继 → 位图； 若题目还要「第 \(k\) 小」或「区间内小于 \(x\) 的个数」→ 树状数组。 两个都会写，看到题面第一眼就能选对。
116.5 替代方案三：堆 + 懒删除¶
只需要最值（不需要任意 \(x\) 的前驱后继）时，这是最简单也最快的方案。
# [片段]
import heapq
class LazyHeap:
"""支持任意元素删除的小根堆（懒删除），均摊 O(log n)。
原理：删除时不真删，只在「待删表」里记一笔；
取堆顶前先把已被标记删除的堆顶弹干净。
"""
def __init__(self):
self.h = [] # 真正的堆，里面可能混着已被标记删除的元素
self.dead = {} # 值 -> 待删次数
self.size = 0 # 逻辑元素个数，通常小于 len(self.h)
def push(self, x):
heapq.heappush(self.h, x)
self.size += 1
def erase(self, x):
"""删除一个值为 x 的元素（调用方保证它存在）。O(1)。"""
self.dead[x] = self.dead.get(x, 0) + 1
self.size -= 1
def top(self):
"""当前最小值；空则返回 None。"""
h, dead = self.h, self.dead # 绑成局部名字，循环里少两次属性查找
while h and dead.get(h[0], 0): # ★ 先把「已死」的堆顶清干净
x = heapq.heappop(h) # 只清堆顶：埋在下面的死元素等它浮上来再说
c = dead[x] - 1
if c:
dead[x] = c # 同值还有待删名额，留着
else:
del dead[x] # 名额用完就抹掉，防止字典越攒越大
return h[0] if h else None
def pop(self):
v = self.top() # 借 top() 先清死元素，之后的堆顶才可信
if v is not None:
heapq.heappop(self.h)
self.size -= 1
return v
| 能力 | 支持？ |
|---|---|
| 插入 / 取最小 / 删任意元素 | ✅ |
| 前驱 / 后继（任意 \(x\)） | ❌ |
| 第 \(k\) 小（\(k > 1\)） | ❌ |
| 值域无限制 | ✅ 这是它唯一的独门优势 |
懒删除的正确性：每个元素最多被 push 一次、pop 一次， 所以 \(m\) 次操作的总代价是 \(O(m\log m)\)，即均摊 \(O(\log m)\)—— 和 Splay 一样是均摊，但常数小两个数量级。
⚠️
dead字典必须记「次数」而不是布尔值，否则重复元素会被多删。
典型用途：Dijkstra 的懒删除（91 章）、 「合并果子」类贪心、对顶堆维护中位数。
对顶堆：维护动态中位数¶
值域无限制、又要「第 \(\lceil n/2 \rceil\) 小」时，用两个堆：
| 堆 | 内容 | 大小约束 |
|---|---|---|
大根堆 lo（存负数模拟） |
较小的一半 | $ |
小根堆 hi |
较大的一半 |
中位数 = -lo[0]。插入后调整一次即可。这是「第 \(k\) 小」在 \(k\) 固定时的 \(O(\log n)\) 特化。
116.6 替代方案四：Counter + 排序（离线）¶
能离线就离线——这是 Python 竞赛的第一原则。
| 场景 | 做法 | 复杂度 |
|---|---|---|
| 所有查询都在所有修改之后 | 一次 sorted + bisect |
\(O(n\log n + q\log n)\) |
| 只需要「每个值出现几次」 | collections.Counter |
\(O(n)\) |
| 插入是批量的、查询在中间 | 按操作序离线 + 树状数组 | \(O((n+q)\log V)\) |
| 需要「排序后的第 \(k\) 个」，但集合不变 | a.sort() 后直接 a[k-1] |
\(O(n\log n)\) 一次 |
# [片段]
from bisect import bisect_left, bisect_right
from collections import Counter
a.sort() # 一次 O(n log n)，Timsort 在 C 层
# 前驱：< x 的最大值
i = bisect_left(a, x) # bisect_left 给出第一个 >= x 的下标
prev = a[i - 1] if i else None # 它左边一格就是最后一个 < x 的；i 为 0 表示没有
# 后继：> x 的最小值
j = bisect_right(a, x) # bisect_right 给出第一个 > x 的下标
succ = a[j] if j < len(a) else None # 越界表示 x 已经是最大值
# x 的出现次数
c = bisect_right(a, x) - bisect_left(a, x) # 两个边界之间夹的正是全部等于 x 的元素
# 区间 [l, r] 内元素个数
c2 = bisect_right(a, r) - bisect_left(a, l) # 闭区间：左端用 left、右端用 right
⚠️
bisect的key=参数是 Python 3.10 才有的，牛客 3.9 不能用。 要按 key 二分，只能自己造「已经映射好的平行数组」，或者把元组排序后二分元组。 见 14-标准库速查。⚠️ 「插入 + 保持有序」不要用
bisect.insort： 它内部是list.insert，\(O(n)\) 的memmove。 \(q = 10^5\) 次insort到长度 \(10^5\) 的列表 = \(10^{10}\) 字节移动，必然 TLE。insort只在 \(q \le 10^4\) 时可用——但那个规模什么方法都行。 详见 05-列表。
116.7 决策表（本章最重要的一节）¶
拿到一个「有序集合」需求，按这张表从上往下找第一个匹配的行：
| 条件 | 方案 | Python 可行规模 |
|---|---|---|
| 所有查询在所有修改之后 | sort + bisect |
\(10^6\) ✅ |
| 只要「出现次数」，不要顺序 | Counter / dict |
\(10^6\) ✅ |
| 只要前驱 / 后继 / 存在性，且值域 \(\le 10^7\) | 两级值域位图 | \(10^6\) ✅ 最快 |
| 值域大但可离线离散化 + 只要前驱后继 | 离散化 + 值域位图 | \(10^6\) ✅ |
| 要第 \(k\) 小 / 排名 / 区间计数，值域 \(\le 10^7\) | 树状数组 + 倍增 | \(10^5\) ✅，\(10^6\) ⚠️ |
| 要第 \(k\) 小，值域大但可离散化 | 同上 | 同上 |
| 只要最值 + 任意删除，值域无限制 | 堆 + 懒删除 | \(10^6\) ✅ |
| 只要固定的第 \(k\) 小（如中位数） | 对顶堆 | \(10^6\) ✅ |
| 「区间内小于 \(x\) 的个数」+ 区间修改 | 分块 + 块内排序副本 | \(10^5\) ⚠️（见 BISHI129） |
| 需要区间翻转 / 区间移动，\(n \le 2\times10^3\) | list 切片暴力 |
✅ |
| 需要区间翻转，\(n \ge 10^4\) | ❌ Python 放弃 | — |
| 值域无限、在线、要任意前驱后继、\(n \le 3\times10^3\) | list + insort 暴力 |
✅ |
| 值域无限、在线、要任意前驱后继、\(n \ge 10^5\) | ❌ Python 基本无解 | — |
| 任何情况 | ❌ 不要手写 Splay / Treap / 跳表 | — |
| 任何情况 | ❌ 不要 import sortedcontainers（判题机没装） |
— |
这张表的两条主线： 1. 先问「能不能离线」——能离线就
sort+bisect，一切从简； 2. 在线的话先问「值域多大」——值域小就开值域结构， 再问「要不要第 \(k\) 小」来决定位图还是树状数组。「值域」是 Python 选手看题面时最该先找的那个数。 BISHI4 的 \(0 \le x \le 10^6\)、BISHI5 的 \(|x| \le 10^6\)、 BISHI129 的 \(|a_i| \le 10^7\) —— 出题人把值域写出来就是在给提示。
116.8 例题¶
BISHI5 【模板】多重集合操作（简单）¶
维护初始为空的多重集合，\(n \le 10^5\) 次操作，\(|x| \le 10^6\)： 1 插入、2 删除一个、3 查询 \(x\) 的个数、4 查询总个数（含重复）、 5 前驱（严格小于 \(x\) 的最大元素）、6 后继（严格大于 \(x\) 的最小元素）； 5/6 不存在输出 \(-1\)。 时限：C/C++ 1 秒，其他语言 2 秒。 题面见 BISHI5 原题（牛客）。
✅ 题解见
solutions/BISHI5.py，已通过官方样例验证。 本题在 34-集合与多重集合 是主讲； 这里作为「平衡树的 Python 替身」的实证再看一遍。
这题就是 std::multiset 的模板题，C++ 三行搞定。
Python 没有内置有序集合、又不能用 sortedcontainers，
所以它恰好是本章全部论点的检验场。
四种方案在本题上的对照：
| 方案 | 单次代价 | \(n = 10^5\) 总量 | 判断 |
|---|---|---|---|
Counter + 每次 sorted |
\(O(k\log k)\) | 爆炸 | ❌ |
| 堆 + 懒删除 | — | — | ❌ 无法回答任意 \(x\) 的前驱后继 |
| 树状数组 + 倍增 | \(O(\log V) \approx 21\) | \(2\times10^6\) 次 Python 层迭代 | ⚠️ 2 秒下偏险 |
| 计数字典 + 两级位图 | \(O(1)\) | \(\approx 3\times10^5\) 次 C 层运算 | ✅ 选它 |
| 手写 Splay | \(O(\log n)\) 但常数 30× | \(10^8\) | ❌ |
值域 \(|x| \le 10^6\) → 平移 \(+10^6\) 后固定为 \([0, 2\times10^6]\)， 共 \(2\times10^6 / 1024 + 1 = 1954\) 块。值域小且固定，这是位图能用的前提； 而且本题是在线操作，也不方便离线离散化。
import sys
OFFSET = 10 ** 6 # 把 [-1e6, 1e6] 平移到 [0, 2e6]
BITS = 1024 # 每块 1024 个值，即一个 1024 位的大整数
NBLK = (2 * 10 ** 6) // BITS + 1 # 1954 块
def main() -> None:
data = sys.stdin.buffer.read().split(b"\n") # 按行切：操作行的 token 数不固定
n = int(data[0])
cnt = {} # 值 -> 出现次数（只存 > 0 的）
blk = [0] * NBLK # 位图：该值是否存在
summ = 0 # 哪些块非空
total = 0 # 含重复的元素总数
out = []
for k in range(1, n + 1): # 第 0 行是 n，操作从第 1 行起
p = data[k].split()
op = p[0] # 与 bytes 直接比较，省去一次 int() 转换
if op == b"4": # 总个数（含重复）
out.append(str(total))
continue
x = int(p[1]) + OFFSET # 平移到非负，位图下标不能是负数
b, r = divmod(x, BITS) # b 是块号，r 是块内位号
if op == b"1": # 插入一个
c = cnt.get(x, 0)
cnt[x] = c + 1
total += 1
if c == 0: # 第一次出现才点亮位图
blk[b] |= 1 << r
summ |= 1 << b
elif op == b"2": # 删除一个
c = cnt.get(x, 0)
if c:
total -= 1
if c == 1: # 归零才熄灭位图
del cnt[x]
v = blk[b] & ~(1 << r)
blk[b] = v
if v == 0:
summ &= ~(1 << b)
else:
cnt[x] = c - 1
elif op == b"3": # 该值出现次数
out.append(str(cnt.get(x, 0)))
elif op == b"5": # 前驱：< x 的最大值
low = blk[b] & ((1 << r) - 1) # 本块中小于 x 的部分
# 掩码保留第 0..r-1 位，天然排除 x 自己
if low:
# 最高位的 1 就是本块里离 x 最近的那个较小值
out.append(str(b * BITS + low.bit_length() - 1 - OFFSET))
else:
s = summ & ((1 << b) - 1) # 更左边的非空块
if s:
bb = s.bit_length() - 1 # 最靠右的那个非空块，即最近的左邻
# 该块整体都比 x 小，取它的最高位即可
out.append(str(bb * BITS + blk[bb].bit_length() - 1 - OFFSET))
else:
out.append("-1") # 左边一个非空块都没有
else: # 6 后继：> x 的最小值
hi = blk[b] >> (r + 1) # 本块中大于 x 的部分
# 右移 r+1 位，把第 r 位及以下全丢掉
if hi:
# lowbit 定位到 hi 的最低位 1，加回被移走的 r+1 个位置
out.append(str(x + 1 + (hi & -hi).bit_length() - 1 - OFFSET))
else:
s = summ >> (b + 1) # 更右边的非空块
if s:
bb = b + 1 + (s & -s).bit_length() - 1 # 最近的右邻非空块
v = blk[bb]
# 该块整体都比 x 大，取它的最低位即可
out.append(str(bb * BITS + (v & -v).bit_length() - 1 - OFFSET))
else:
out.append("-1") # 右边一个非空块都没有
sys.stdout.write("\n".join(out) + "\n")
main()
六个坑（来自题解的踩坑记录）：
- 前驱/后继是严格小于/大于 \(x\)，且与 \(x\) 自身在不在集合里无关；
- 输出的是原始值，别忘了减回
OFFSET； - \(x\) 可以是负数，必须平移后再进位图；
- 删除不存在的元素要静默忽略，且不能把
total减成负数； - 操作 4 这一行的格式不固定（样例里是
4 0，题面说每行两个整数）—— 所以按行split()解析而不是按 token 游标盲读，两种格式都吃得下； - 操作 3 查的是「该值出现次数」（可能是 0），操作 4 查的是「含重复的总个数」—— 两个都容易和「不同值的个数」搞混。
回到 S4 的那份 Splay API 清单，逐条对照本题解：
S4 Splay 常用版 本题解的实现 复杂度 Insert(key)cnt[x] += 1+ 点亮位图\(O(1)\) Delete(key)cnt[x] -= 1+ 可能熄灭位图\(O(1)\) find(key)cnt.get(x, 0)\(O(1)\) prev()块内取最高位 / summ找左邻块\(O(1)\) succ()块内取 lowbit / summ找右邻块\(O(1)\) GetPth(p)（第 \(k\) 小）❌ 位图做不到 → 换树状数组 \(O(\log V)\) GetRank(key)（排名）❌ 同上 \(O(\log V)\) 7 个操作里 5 个被降到了 \(O(1)\)，另 2 个交给树状数组。 这就是「Python 不写平衡树」的完整技术依据。
BISHI129 区间增量与区间小于计数（中等）¶
\(n, q \le 10^5\)，\(|a_i| \le 10^7\)。
1 l r x：\(\forall i\in[l,r],\ a_i \mathrel{+}= x\)；2 l r x：输出 \(\sum_{i=l}^{r}\mathbf{1}_{a_i < x}\)，\(|x| \le 10^9\)。 时限：C/C++ 5 秒，其他语言 10 秒；空间 1024 MB。 题面见 BISHI129 原题（牛客）。✅ 题解见
solutions/BISHI129.py，已通过官方样例验证。 本题在 39-树状数组与线段树 也有讲解（分块视角）； 这里从「有序集合的分布式版本」视角看。
这题是「有序集合」需求的一个变形：不是全局有序集合， 而是每个块维护一份局部有序集合。
为什么不能用线段树：「区间内小于 \(x\) 的个数」不可合并—— 阈值 \(x\) 是查询时才给的，两个子区间的答案无法预先合并成父区间的答案。 线段树节点存不下有用信息（除非套一棵内层树，那是树套树 \(O(\log^2 n)\)，Python 更没戏）。
为什么不能用全局有序集合：查询限定在下标区间 \([l,r]\) 上， 而位图/树状数组是按值域组织的，丢掉了下标信息。
正解：分块 + 块内排序副本。每块额外维护两样东西：
| 字段 | 含义 |
|---|---|
srt[b] |
块内元素的排序副本（就是一个小型有序集合） |
off[b] |
该块的整体偏移（整块加法只改这个数） |
| 操作 | 整块 | 散块 |
|---|---|---|
| 区间加 | off[b] += x，排序副本不动（整体平移不改变相对顺序） |
逐个改后重排该块 |
| 小于计数 | bisect_left(srt[b], x - off[b])，C 层二分 |
逐个比较 |
「整块加不用重排、比较时把阈值反向平移」是分块维护有序信息的核心技巧。 它把「加法」这个破坏有序性的操作，变成了「不影响有序性的整体平移」。 同一招在莫队、分块套
bisect的题里反复出现。
import sys
from bisect import bisect_left
def main() -> None:
data = sys.stdin.buffer.read().split()
n = int(data[0]); q = int(data[1])
a = [int(v) for v in data[2:2 + n]]
S = 400 # 块长，需按实测调优
nb = (n + S - 1) // S # 块数：向上取整，最后一块可能不满
off = [0] * nb # off[b] = 第 b 块的整体偏移量
srt = [sorted(a[b * S:(b + 1) * S]) for b in range(nb)] # 每块一份排序副本
p = 2 + n # 跳过 n、q 与 n 个初值
out = []
push = out.append
for _ in range(q):
op = data[p]
l = int(data[p + 1]) - 1 # 题面下标从 1 起，这里统一转成 0-indexed
r = int(data[p + 2]) - 1
x = int(data[p + 3])
p += 4 # 两种操作都是 4 个 token
bl = l // S # 左端点所在块
br = r // S # 右端点所在块
if op == b"1": # ---- 区间加 ----
if bl == br: # 首尾同块：整段都是散块，逐个改
a[l:r + 1] = [t + x for t in a[l:r + 1]]
srt[bl] = sorted(a[bl * S:(bl + 1) * S]) # 散块改过就必须重排副本
else:
e = (bl + 1) * S # 左边散块的右边界（下一块的起点）
a[l:e] = [t + x for t in a[l:e]]
srt[bl] = sorted(a[bl * S:e])
for b in range(bl + 1, br): # 整块只改偏移，排序副本不动
off[b] += x # 整体平移不改变块内相对顺序，这是全题的关键
s = br * S # 右边散块的左边界
a[s:r + 1] = [t + x for t in a[s:r + 1]]
srt[br] = sorted(a[s:min(s + S, n)]) # 末块可能不满，用 min 截断
else: # ---- 小于 x 计数 ----
if bl == br:
v = x - off[bl] # 阈值反向平移，抵消该块欠着的偏移
cnt = sum(map(v.__gt__, a[l:r + 1])) # v.__gt__(t) 即 t < v
else:
e = (bl + 1) * S
v = x - off[bl]
cnt = sum(map(v.__gt__, a[l:e])) # 左散块：C 层逐个比较
for b in range(bl + 1, br):
cnt += bisect_left(srt[b], x - off[b]) # C 层二分
# 副本没动过，二分结果依然有效
s = br * S
v = x - off[br]
cnt += sum(map(v.__gt__, a[s:r + 1])) # 右散块
push(cnt)
sys.stdout.write("\n".join(map(str, out)) + "\n")
main()
Python 关键：散块必须下沉到 C 层。
| 写法 | 代价 |
|---|---|
❌ for t in a[l:e]: if t < v: cnt += 1 |
\(10^5\) 次查询 \(\times\ 2S\) 次 Python 层比较 \(\approx 10^8\) → 60 秒起步 |
✅ sum(map(v.__gt__, a[l:e])) |
v.__gt__(t) 就是 t < v，map + sum 全在 C 层，快 3–5 倍 |
✅ a[l:e] = [t + x for t in a[l:e]] |
列表推导式比逐个下标赋值快 3 倍 |
四个坑：
- 整块的比较阈值是 \(x - \text{off}[b]\)（把偏移反向平移到阈值上），不是 \(x\)；
- 散块改完必须重建该块的排序副本，忘了就 WA；
- 是「小于」不是「小于等于」，所以用
bisect_left； - 单块内（
bl == br）要单独走一条分支，不能套用三段式。
⚠️ Python 现实性：险。 整块二分（\(n/S \approx 250\) 次
bisect调用）+ 散块 C 层扫描， 实测每次查询 50–100 μs 量级，\(10^5\) 次就是 5–10 秒，贴着 10 秒上限。 块长 \(S\) 需要按实测在 \([300, 700]\) 之间调优。 这是 00-知识大纲 明确标记的语言劣势题之一。如果把它换成平衡树套平衡树（树套树），Python 是 \(10^8\) 量级 → 完全没戏。 分块之所以能救命，正是因为它把「\(\log\)」换成了「C 层的
bisect与切片」。
想练手平衡树的话¶
牛客题单里没有平衡树题。想练：
| 想练 | 推荐题 | Python 可行性 |
|---|---|---|
| 有序集合全套操作 | 洛谷 P3369【模板】普通平衡树 | ✅ 用值域位图 + 树状数组，比 Splay 快 |
| 区间翻转（文艺平衡树） | 洛谷 P3391【模板】文艺平衡树 | ❌ Python 不现实（\(n \le 10^5\)） |
| 动态第 \(k\) 小 | 洛谷 P3834（主席树）/ P2617 | ⚠️ 整体二分，见 118 章 |
| 区间小于计数 | 洛谷 P2801 教主的魔法 | ✅ 分块 + bisect，同 BISHI129 |
116.9 本章速查¶
| 要点 | 结论 |
|---|---|
| BST 的性质来源 | 中序遍历 = 升序 |
| BST 删除（两个孩子） | 用右子树最小值（后继）覆盖自己，再删那个后继 |
| 为什么后继一定好删 | 它必无左孩子，落回前两种情况 |
| BST 的致命缺陷 | 有序插入退化成链，单次 \(O(n)\) |
| 「有序插入」有多常见 | 最常见（数组本来有序 / 先排了序） |
| 修复退化的三条路 | 旋转（AVL/红黑）、随机化（Treap/跳表）、均摊（Splay） |
| Splay 的唯一动作 | 访问过的节点旋到根 |
| 三种旋转 | zig（单旋）、zig-zig（先转父亲再转自己）、zig-zag |
| zig-zig 写反的后果 | 均摊从 \(O(\log n)\) 退化到 \(O(n)\) |
| Splay 的复杂度保证 | 只保证均摊，单次可以是 \(O(n)\) |
| 均摊分析工具 | 势能法，\(\Phi = \sum \log \operatorname{size}(x)\) |
| Splay 的自适应红利 | 频繁访问的元素待在根附近 |
| Python 手写平衡树的上限 | \(n, q \le 3\times10^3\)（这个规模 list 暴力也能过） |
sortedcontainers |
❌ 判题机没装，禁止依赖 |
int.bit_count() |
❌ Python 3.10+，牛客 3.9 不能用 → bin(v).count("1") |
bisect(key=) |
❌ Python 3.10+，不能用 |
bisect.insort |
⚠️ 内部是 \(O(n)\) 的 list.insert，只在 \(q \le 10^4\) 时可用 |
| 首选方案 | 两级值域位图：前驱/后继/插入/删除全 \(O(1)\) |
| 位图的两级 | blk[b]（1024 位大整数）+ summ（哪些块非空） |
| 位图为什么快 | 所有循环都消失了，全是 C 层大整数运算 |
| 多重集合怎么办 | 位图管有序性 + dict 管重数，两者分离 |
| 位图的局限 | 值域必须 \(\le 10^7\)；不擅长第 \(k\) 小 / 区间计数 |
| **要第 \(k\) 小 → ** | 树状数组 + 倍增，\(O(\log V)\) |
kth 千万不要写成 |
二分答案 + 查前缀和（\(O(\log^2 V)\)） |
| 只要最值 + 任意删除 | 堆 + 懒删除，值域无限制 |
| 懒删除的坑 | dead 字典必须记次数而非布尔 |
| 固定的第 \(k\) 小（中位数） | 对顶堆 |
| 能离线就离线 | sort + bisect，一切从简 |
| 看题面先找哪个数 | 值域（BISHI4/5 的 \(10^6\) 是明示） |
| 区间小于计数 + 区间加 | 分块 + 块内排序副本 + 整体偏移 |
| 分块的核心技巧 | 整块加只改 off，比较时把阈值反向平移 |
| 散块必须怎么写 | sum(map(v.__gt__, a[l:e])) —— 下沉到 C 层 |
| Splay 唯一无替代的场景 | 区间翻转 / 区间移动（文艺平衡树） |
| 数据规模 → Python 现实性（有序集合需求） |
|---|
离线 sort + bisect，\(n \le 10^6\) |
| 值域位图（前驱后继），\(n \le 10^6\) |
| 树状数组 + 倍增（第 \(k\) 小），\(n \le 10^5\) |
| 树状数组 + 倍增，\(n \le 10^6\) |
| 堆 + 懒删除，\(n \le 10^6\) |
| 分块 + 块内排序副本，\(n=q\le10^5\) |
list + insort 暴力，\(q \le 10^4\) |
| 手写 Splay / Treap，\(n \ge 10^4\) |
| 树套树，\(n \ge 10^5\) |
| 区间翻转（文艺平衡树），\(n \ge 10^4\) |
| LCT / 动态树 |