第 41 章 桶计数与离散化¶
配套例题：BISHI24 谐距下标对、BISHI118 相差不超过 k 的最多数 来源：S4
模板.docx排序章「桶排序」；S2useful algorithm/
比较排序的下界是 \(O(n\log n)\)——这是信息论决定的，\(n!\) 种排列至少需要 \(\log_2(n!) = \Theta(n\log n)\) 次比较才能区分。
要突破这个下界，只有一条路：不比较，直接用值当下标。 这就是本章的全部内容：桶、计数排序、基数排序，以及当值域太大时的补救手段——离散化。
41.1 桶：用值当下标¶
「桶」不是一种算法，而是一种数据摆放方式：开一个长度等于值域的数组 cnt，
把值 \(v\) 的信息记在 cnt[v] 里。它把「查找一个值」从 \(O(\log n)\) 降到 \(O(1)\)。
MAXV = 10 ** 5
cnt = [0] * (MAXV + 1) # 值域已知且不大 -> 用 list；长度 MAXV+1 才能容纳下标 MAXV
for x in a:
cnt[x] += 1 # 值直接当下标，O(1) 定位，不需要任何比较
桶能用的前提只有一条：值域 \(V\) 必须开得下。
| 值域 \(V\) | list 桶 |
判断 |
|---|---|---|
| \(\le 10^6\) | 8 MB | ✅ 放心用 |
| \(10^7\) | 80 MB | ⚠️ 用 bytearray / array 压一压 |
| \(\ge 10^8\) | 800 MB+ | ❌ 必须换 dict 或离散化 |
list 与 dict 的取舍：
list 桶 |
dict / Counter |
|
|---|---|---|
| 访问 | 数组下标，最快 | 哈希，慢 2–3 倍 |
| 内存 | \(O(V)\) | \(O(n)\) |
| 负数 / 稀疏值 | 要手动偏移 | 直接支持 |
| 适用 | 值域小且稠密 | 值域大或稀疏 |
负数偏移是
list桶最常见的 bug 来源。若值域是 \([-10^5, 10^5]\)， 必须写cnt[x + OFFSET]，且数组长度是 \(2V+1\)。 忘了偏移会得到「负下标从尾部回绕」——Python 不会报错，只会静默算错。 这一点比 C++ 更危险（C++ 至少会崩）。
41.2 计数排序¶
值域小的时候，排序可以是 \(O(n + V)\) 的：数一遍，再按值从小到大把桶倒出来。
def counting_sort(a, lo, hi):
"""对值域在 [lo, hi] 的整数数组排序，O(n + (hi - lo))。"""
cnt = [0] * (hi - lo + 1) # 闭区间 [lo, hi] 共 hi-lo+1 个值
for x in a:
cnt[x - lo] += 1 # 减 lo 完成偏移：值 lo 落在下标 0
res = []
for v, c in enumerate(cnt): # enumerate 天然按下标升序 = 按值升序
if c:
res.extend([v + lo] * c) # 加回 lo 还原真实值；整段扩展，循环下沉到 C 层
return res
| 对比 | 计数排序 | sorted |
|---|---|---|
| 复杂度 | \(O(n + V)\) | \(O(n\log n)\) |
| 值域要求 | 必须小 | 无 |
| Python 实测（\(n=10^5\)，\(V=10^5\)） | 约 0.03 s | 约 0.02 s |
注意这个实测结果：计数排序在 Python 里并不比
sorted快。 因为sorted的 \(n\log n\) 全在 C 层，而计数排序的for x in a是 Python 层循环。 只有当 \(V \ll n\)（大量重复元素）时，计数排序才有优势：from collections import Counter cnt = Counter(a) # C 层计数，这才是 Python 的正确姿势 res = [] for v in sorted(cnt): res.extend([v] * cnt[v])结论：Python 里几乎不需要手写计数排序。它真正的价值是 「用桶做统计」这个思路，而不是「用桶来排序」这个动作。
稳定版计数排序（前缀和定位）¶
基数排序要用到稳定版，写法是先对 cnt 求前缀和，得到每个值的起始写入位置：
def counting_sort_stable(a, key, k):
"""按 key(x) in [0, k) 稳定排序，O(n + k)。"""
cnt = [0] * (k + 1) # 多开一位，配合下面的错位写入
for x in a:
cnt[key(x) + 1] += 1 # 错位一格：把「键 v 的个数」记到 cnt[v+1]
for i in range(1, k + 1):
cnt[i] += cnt[i - 1] # 求前缀和后，cnt[v] 恰是键 v 的第一个写入位置
res = [None] * len(a)
for x in a: # 正序遍历 + 起始位置递增 = 稳定
res[cnt[key(x)]] = x # 写到该键当前的空位
cnt[key(x)] += 1 # 空位后移，下一个同键元素排在它后面
return res
41.3 桶排序与基数排序¶
桶排序¶
把值域切成 \(m\) 段，每段一个桶，元素进桶后桶内各自排序，最后按桶顺序拼接。 当数据在值域上均匀分布时期望 \(O(n)\)；分布倾斜时退化成一个桶装全部，\(O(n\log n)\)。
竞赛中桶排序基本不用，但它的思想在分块里复活了，见 39-树状数组与线段树 的分块一节。
基数排序（LSD）¶
从低位到高位，对每一位做一次稳定排序。因为每趟都稳定，高位排完时低位的相对顺序 被保留下来，最终整体有序。
def radix_sort(a, base=1 << 16):
"""非负整数的 LSD 基数排序，每轮处理 16 个二进制位。"""
if not a:
return a
mx = max(a) # 最大值决定要处理多少轮
exp = 1 # exp 是当前处理的那一位的权重，逐轮乘 base
while mx // exp > 0: # 最高位处理完后 mx // exp 变 0，循环结束
cnt = [0] * (base + 1)
for x in a:
cnt[(x // exp) % base + 1] += 1 # 取出当前这一位的值，错位一格计数
for i in range(1, base + 1):
cnt[i] += cnt[i - 1] # 前缀和 = 每个桶的起始写入位置
res = [0] * len(a)
for x in a: # 正序遍历保证本轮稳定，低位的相对顺序才不会被打乱
d = (x // exp) % base
res[cnt[d]] = x
cnt[d] += 1
a = res
exp *= base # 进到更高的一组位
return a
在 Python 里基数排序一定比
sorted慢（好几倍），因为每一趟都是纯 Python 循环。 写它的唯一理由是理解「多关键字排序 = 从次要到主要倒着排若干趟稳定排序」—— 这条原理在实战中是有用的，见 12-自定义排序 §12.7： 当降序字段是字符串、负号技巧失效时，两趟稳定sort就是 LSD 基数排序的直系应用。
41.4 离散化：值域太大时的标准解法¶
离散化 = 把「值」换成「值的排名」，在保持大小关系的前提下把值域压到 \([0, n)\)。
适用场景：
- 值域 \(10^9\) 但元素只有 \(10^5\) 个，要开桶 / 树状数组 / 线段树；
- 只关心元素之间的相对大小，不关心具体数值；
- 求逆序对、区间第 \(k\) 大、扫描线的坐标压缩。
模板一：sorted(set(...)) + bisect（最常用）¶
from bisect import bisect_left
vals = sorted(set(a)) # 去重并排序，vals[i] 是第 i 小的值
rank = {v: i for i, v in enumerate(vals)} # 值 -> 排名，O(1) 查；只对出现过的值有效
b = [rank[x] for x in a] # 离散化后的数组，取值在 [0, len(vals))
# 若还要处理「查询里出现、但原数组没有的值」，用 bisect 而不是 dict（dict 会 KeyError）
pos = bisect_left(vals, x) # 第一个 >= x 的排名，即 x 应该插在哪里
| 步骤 | 复杂度 |
|---|---|
sorted(set(a)) |
\(O(n\log n)\) |
建 rank 字典 |
\(O(n)\) |
| 映射整个数组 | \(O(n)\) |
单次 bisect_left |
\(O(\log n)\) |
dict还是bisect？ 只需要映射原数组里出现过的值 → 用dict，\(O(1)\) 更快； 还要映射任意查询值（比如「有多少个数 \(\le x\)」）→ 必须用bisect。
模板二：不去重的离散化¶
有些题要求「相等的元素排名也不同」（比如按输入顺序定序），这时不去重：
order = sorted(range(n), key=lambda i: a[i]) # 排的是下标，值相等时按下标先后（sort 稳定）
rank = [0] * n
for r, i in enumerate(order):
rank[i] = r # 反过来填：原位置 i 拿到唯一排名 r
模板三：多个数组一起离散化¶
坐标压缩时常见（比如线段树上要同时容纳左右端点）：
三个高频坑： 1. 忘了去重。
sorted(a)不去重时，相等的值会占多个排名， 树状数组的下标就对不上了。 2. 排名从 0 还是从 1。树状数组要求下标从 1 开始（lowbit(0) = 0会死循环）， 所以配合树状数组时写rank[x] + 1。 3. 离散化后不能再做算术。排名只保序，不保差值——rank[5] - rank[3]没有任何意义。凡是要用到「差值 \(\le k\)」的题， 离散化必须只用于建桶，判断仍要用原值。BISHI118 就是这个套路。
41.5 桶思想的三个变形¶
| 变形 | 做法 | 典型用途 |
|---|---|---|
| 值域桶 | cnt[v] += 1 |
出现次数、众数 |
| 前缀桶 | cnt 求前缀和 |
「有多少个数 \(\le v\)」\(O(1)\) 查 |
| 差值桶 | 把 \(a_i - i\)、\(a_i + i\) 之类当键 | 把二元条件降成一元，BISHI24 |
第三种最容易被忽略，却是笔试题的高频套路。口诀是：
看到「统计满足 \(f(i, j) = 0\) 的下标对数」，先试着把条件移项成 \(g(i) = g(j)\)。 一旦成功，问题立刻从 \(O(n^2)\) 枚举掉到 \(O(n)\) 哈希计数。
41.6 例题¶
BISHI24 谐距下标对（入门）¶
长度 \(n\ (1 \le n \le 10^5)\) 的数组（\(1 \le a_i \le 10^5\)）， 求满足 \(i < j\) 且 \(a_j - a_i = j - i\) 的下标对数量。 题面见 BISHI24 原题（牛客）。
移项：
于是定义 \(b_i = a_i - i\)，问题变成「有多少对下标满足 \(b_i = b_j\)」。 每个大小为 \(c\) 的相同值分组贡献 \(\binom{c}{2} = \dfrac{c(c-1)}{2}\) 对：
import sys
from collections import Counter
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
# 条件 a_j - a_i = j - i 移项成 a_j - j = a_i - i，于是把 b_i = a_i - i 当键计数
# data[1+i] 是第 i 个元素（0-indexed），减的下标 i 与它一致，偏移量常数不影响相等判定
cnt = Counter(int(data[1 + i]) - i for i in range(n)) # 差值桶
# 同一组里任取两个下标都构成一对，大小为 c 的组贡献 C(c,2) 对
print(sum(c * (c - 1) // 2 for c in cnt.values()))
main()
三个要点：
- 用
Counter而不是list桶：\(b_i = a_i - i\) 的取值范围是 \([1 - (n-1),\ 10^5]\)，会是负数。用list就得手动偏移 \(n\)， 多一处出错机会；Counter直接支持任意键。 - 只需要分组，不需要顺序，所以是 \(O(n)\) 的哈希计数而不是 \(O(n\log n)\) 的排序。
- \(\binom{c}{2}\) 用
c * (c - 1) // 2，整除不会有浮点误差。
题解见 solutions/BISHI24.py，
排序视角的对照写法见
12-自定义排序 §12.12。
BISHI118 相差不超过 k 的最多数（中等）¶
给 \(n\ (1 \le n \le 2\times10^5)\) 个正整数（\(1 \le a_i \le 10^9\)）， 选出若干个数使 \(\max(S) - \min(S) \le k\ (1 \le k \le 10^9)\)，求最多能选几个。 题面见 BISHI118 原题（牛客）。
关键观察：既然只约束了最大值与最小值的差，那么排序之后，答案一定是一段连续区间—— 若选了 \(x\) 和 \(y\)（\(x < y\)，\(y - x \le k\)），那么所有介于两者之间的数也都能加进来， 只会更优。于是问题变成「排序后求最长的、首尾差 \(\le k\) 的连续段」，双指针一遍扫完：
import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); k = int(data[1])
a = sorted(map(int, data[2:2 + n])) # 排序本身就是最轻量的离散化：值换成位置
ans = 0
l = 0 # 窗口左端，只增不减
for r in range(n):
# 数组有序，所以 a[r] - a[l] 就是窗口内的极差；比较用的是原值而非排名
while a[r] - a[l] > k: # 右端进来后把左端推到合法位置
l += 1
if r - l + 1 > ans: # 循环不变量：此刻 [l, r] 合法且 l 最小
ans = r - l + 1
# l、r 各自最多走 n 步且都不回退，总复杂度 O(n)（排序的 O(n log n) 才是瓶颈）
print(ans)
main()
为什么这题放在桶计数章：因为它演示了值域桶失效时该怎么办。
| 若 \(a_i \le 10^5\) | 若 \(a_i \le 10^9\)（本题） |
|---|---|
开桶 cnt[v]，求前缀和 pre[v] |
桶开不下（8 GB） |
| 答案 \(= \max_v\ (pre[v+k] - pre[v-1])\)，\(O(V)\) | 离散化的极简形态：排序 + 双指针 |
也就是说，排序本身就是最轻量的离散化——它把「值」换成了「位置」， 而双指针在位置上滑动，等价于在压缩后的值域上滑动。
注意 41.4 提到的第三个坑在这里体现得很清楚： 判断
a[r] - a[l] > k用的是原值，不是排名。 如果先把a离散化成排名再比较差值，答案会完全错——排名不保差值。
双指针的完整框架、为什么总复杂度是 \(O(n)\)，见 43-双指针与滑动窗口。 本题在 BISHI118 的题解文件尚未建立时，上面这份代码已用官方样例实测通过。
41.7 本章速查¶
| 场景 | 做法 |
|---|---|
| 值域 \(\le 10^6\) | list 桶，最快 |
| 值域大 / 稀疏 / 有负数 | Counter 或 dict |
list 桶 + 负数 |
必须手动偏移，Python 不报错只算错 |
| 计数排序 | \(O(n+V)\)；Python 里不比 sorted 快，除非 \(V \ll n\) |
| 基数排序 | 教学价值 > 实战价值；其原理 = 多趟稳定排序 |
| 值域大要开数据结构 | 离散化：sorted(set(a)) + rank 字典 |
| 要查任意值的排名 | 用 bisect_left(vals, x)，不能用 dict |
| 配合树状数组 | 排名 +1，下标从 1 开始 |
| 离散化后 | 只保序不保差值，差值判断必须用原值 |
| 统计 \(f(i,j)=0\) 的对数 | 先移项成 \(g(i) = g(j)\)，再哈希计数 \(O(n)\) |
| 只约束 \(\max - \min\) | 排序后答案必是连续段 → 双指针 |
| 模板 | 位置 |
|---|---|
| 计数排序 / 稳定计数排序 | §41.2 |
| 基数排序 LSD | §41.3 |
| 离散化（去重 / 不去重 / 多数组） | §41.4 |