Wavelet Tree

构造 ​

对序列公理库序列Sequence以自然数为定义域的函数。 $S[0..n)$、有序字母表 $[0,\sigma )$，根把字母表分成左右两半，并写位向量 $B$: 元素进左半记 0、右半记 1；按位稳定分割得到两个子序列，递归直到单字母。平衡树高度 $\lceil \log \sigma \rceil$，所有层位数共 $n\log \sigma$。

位置映射 ​

access$(i)$ 读根位 $b=B[i]$，到相应孩子的位置是 rank${}_b(B,i)$，沿路恢复字符。rank${}_c(i)$ 按字符 $c$ 的固定路径映射前缀长度；select 从叶向上，用 select${}_b$ 逆映射。若节点位向量常数时间 rank/select，三种操作均为 $O(\log \sigma )$。

区间第 k 小 ​

对半开区间 $[l,r)$，左子区间元素数是

$$z={\mathrm{rank}}_0(r)-{\mathrm{rank}}_0(l).$$

若 $k\le z$ 就映射到左子区间，否则令 $k\leftarrow k-z$ 并进右子区间。日志查询中这可直接求时间区间内第 $k$ 小状态码，不必抽取排序。

边界与消歧 ​

rank 端点若一处含 $i$、一处不含，会让位置逐层漂移。空间 $n\log \sigma +o(n\log \sigma )$ 是平衡形态；Huffman-shaped、wavelet matrix 和熵压缩需另写保证。动态更新要维护各层位向量，不由静态结构自动支持。Wavelet tree 与信号处理的小波变换只同名，不做数值基函数分解。

构建与范围计数 ​

每层稳定 partition 全序列一次，平衡树构建时间 $O(n\log \sigma )$；若字母表先坐标压缩，还要计排序/映射。节点位向量总长度每层恰为 $n$，因此基础 bit 数是 $n\lceil \log \sigma \rceil$。

区间内值落在 $[a,b]$ 的计数可沿字母表树递归：节点字母区间完全包含就返回当前位置区间长度，不交则零，部分相交时用 rank 映射到孩子。时间 $O(\log \sigma )$ 的典型界依查询值区间的树分解，报告所有位置仍需加输出成本。

区间映射的完整轨迹 ​

在节点位向量 $B$ 上，父区间 $[l,r)$ 映到左孩子为

$$[{\mathrm{rank}}_0(l),{\mathrm{rank}}_0(r)),$$

映到右孩子为 $[{\mathrm{rank}}_1(l),{\mathrm{rank}}_1(r))$。区间长度始终等于当前字母范围内的元素数，这是沿层递归的核心不变量。

求第 $k$ 小时先计算左段数量 $z=ran{k}_0(r)-ran{k}_0(l)$。若 $k\le z$，携原 $k$ 进入左孩子；否则进入右孩子并令 $k\leftarrow k-z$。到叶时字母范围只剩一个值，它就是答案。若 $k$ 从 1 开始，判断必须是 $k\le z$；改成 0-based 时条件和减量要一起改。

构建每层必须稳定分割，否则下一层位置不再对应原区间的相对次序。动态插入不仅要在根位向量插一位，还要沿路径在子序列对应位置插入，静态 packed bit vector 的空间与时间结论不能原样复用。

参考资料

• Roberto Grossi, Ankur Gupta, Jeffrey Vitter, High-Order Entropy-Compressed Text Indexes, SODA, 2003.
• Gonzalo Navarro, Wavelet Trees for All, Journal of Discrete Algorithms, 2014.