编程面试：如何用 Wavelet Matrix 支持区间第 k 小？
题干与适用场景
给定静态整数数组 a，需要回答大量半开区间 [l, r) 查询：返回第 k 小的值、区间内等于 x 的频次，以及落在 [lo, hi) 的元素个数。数组不更新，值域可能很大。请设计并分析一种比每次排序更快的结构。
Wavelet Matrix 将每个值按二进制位从高到低稳定划分，在每一层保存一个位向量及其前缀 1 的数量。它不需要显式树指针，查询时把区间映射到下一层。强回答要先明确 k 是 0-based，处理坐标压缩和重复值，再给出时间与空间边界。
面试官考察点
- 是否能说明稳定划分、零段起点和 rank 映射为何保持相对顺序。
- 是否能在
[l, r)上沿位层选择第 k 小并正确累积答案。 - 是否处理重复值、空区间、
k越界和负数值。 - 是否区分值域计数、单值频次与第 k 小的查询路径。
- 是否给出
O(B)查询、O(nB)构建和可压缩空间的复杂度。 - 是否知道静态结构不天然支持高效更新，以及何时应换成其他结构。
回答前需要澄清的问题
- 查询中的
r是否为排他端点？k是从 0 还是从 1 开始？ - 数组是否真的不会更新？若有更新，更新频率和查询频率是多少？
- 值是否为有符号整数，最大位宽是多少？是否可以先做坐标压缩？
- rank 查询需要多少内存，是否允许分块或 bitvector 压缩？
- 只要第 k 小，还是还需要频次、前驱或区间和？不同操作会改变结构选择。
30 秒回答框架
我会把值压缩到连续的非负编码，设最大位宽为 B。构建时从最高位到最低位稳定地把当前序列分成 0 段和 1 段，同时保存该层的位向量和 rank1 前缀。查询第 k 小时维护 [l,r)，计算这一层的零数量；若 k 小于零数量就映射到零段，否则减去零数量并进入一段，同时在答案中设置当前位。单值频次用两次 rank，值域计数用两次小于计数相减。所有查询为 O(B)，构建为 O(nB)。
分步骤深入解答
1. 编码值域与位宽
若值域是任意有符号整数，可排序去重后映射到 0..m-1，并保存编码到原值的数组。这样 B 为 ceil(log2(m))，还要处理 m 为 1 的情况。若必须保留自然数值，可对有符号最高位做偏移，使按无符号字典序等同于数值序。
2. 稳定划分一层
对当前序列 cur 查看第 bit 位，先把所有 0 放入 next，再把所有 1 放入 next，保持各自原有顺序。位向量 bv[i] 记录原位置 i 的位值，zeroCount 记录本层 0 的总数。稳定性保证后续层的区间映射仍对应原区间中的同一批元素。
rank1(i) = bv[0..i) 中 1 的数量
zeroCount = n - rank1(n)
若当前区间为 [l, r)：
zero 区间 = [l - rank1(l), r - rank1(r))
one 区间 = [zeroCount + rank1(l), zeroCount + rank1(r))3. 查询区间第 k 小
每层先计算 zeros = (r-l) - (rank1(r)-rank1(l))。当 k 小于 zeros 时，把 [l,r) 映射到零区间；否则令 k -= zeros，把区间映射到一段，并把答案的当前位设为 1。处理完 B 层后得到编码，再反向映射为原值。
4. 单值频次
把目标值的每一位当作固定分支，按同样的映射更新 [l,r)。如果某一位目标为 0，进入零区间；为 1，进入一段并加上 zeroCount。完成 B 层后，区间长度就是该值在原区间中的频次。目标值不在压缩表时直接返回 0。
5. 值域计数
定义 countLess(x, l, r) 返回 [l,r) 中小于 x 的元素数。沿位层比较 x 的当前位：当 x 的位为 1 时，当前区间的全部零分支都小于 x，应把 zeros 加入答案，然后继续一分支；为 0 时只继续零分支。于是 [lo, hi) 的计数为 countLess(hi)-countLess(lo)。
6. 边界与验证
空区间和左端点不小于右端点时，应明确返回错误或 0，不能让 rank 数组越界。k 必须落在当前区间长度以内。测试应覆盖全部值相同、严格递增、重复交错、负数、单元素、最大值位宽和压缩表外查询，并与朴素排序或计数结果逐条比对。
7. 复杂度与取舍
若使用普通前缀数组，每层占 O(n) 个计数，空间 O(nB)，构建 O(nB)，每个操作 O(B)。将位向量换成支持 rank 的压缩 bitvector 可降低常数和空间。结构适合静态、多查询场景；需要频繁更新时，可考虑分块 Wavelet Matrix、线段树套有序结构或离线算法，并重新评估内存和更新成本。
高质量示范回答
我先明确查询使用半开区间，k 从 0 开始，数组不更新。值先做坐标压缩，B 是编码的位宽。构建时从高位到低位稳定划分，并为每层保存位向量的 rank1 前缀和零段长度。
第 k 小查询在每层计算当前区间的零数量。k 落在零段就用 l-rank1(l) 和 r-rank1(r) 映射；否则减去零数量，映射到 zeroCount+rank1(l) 与 zeroCount+rank1(r)，并设置答案位。单值频次沿固定值路径，值域计数用两个 countLess 相减。构建和每次查询分别是 O(nB) 与 O(B)，越界和压缩表外值返回明确错误或 0。
常见错误
- 混用闭区间和半开区间 → rank 偏移一位 → 统一使用
[l,r)并写出映射式。 - 忘记稳定划分 → 下一层区间不再对应原元素 → 0 段和 1 段都保持原顺序。
- 选择一段时没有减去零数量 → 第 k 小结果偏大 → 先
k -= zeros再进入一段。 - 直接把有符号数按无符号位序比较 → 负数顺序错误 → 做坐标压缩或翻转符号位。
- 把结构当成支持更新 → 更新会破坏每层排列 → 说明静态前提并选择动态替代方案。
- 只测不同值 → 重复值和边界错误被隐藏 → 加入全相同、交错重复、空区间和越界测试。
追问及应对
为什么不用每次排序？
单次排序需要 O((r-l) log(r-l))，大量查询会重复工作。Wavelet Matrix 预先编码每一层的分支，查询只走 B 层，适合静态数据和高查询量。
rank1 为什么能完成区间映射？
前缀 rank 给出区间左、右端点之前的一段中有多少个 1，因此能分别计算该区间在零段和一段中的相对位置；稳定划分保证这些位置对应同一批元素。
如何支持第 k 大？
把 k 转成区间长度减一再减去 k 的第 k 小，或在每层优先走一分支并相应扣除一数量。两种方式都保持 O(B)。
如果值域远大于 n 怎么办？
对出现值做坐标压缩，并保存编码到原值的映射；查询未出现的值通过二分映射到边界或直接返回频次 0。
需要动态更新时怎么办？
普通 Wavelet Matrix 不适合频繁更新。可采用分块重建、带动态 bitvector 的结构或离线处理；选择取决于更新与查询比例、延迟目标和内存预算。