Wavelet Tree

每层位向量既记录字符落入字母表哪一半，也用 rank 把父序列位置稳定映射到对应子序列。查询携带的位置或区间随路径不断收缩，到叶便恢复字符；区间第 $k$ 小则用左侧元素数决定进入哪一半并调整秩。

边界与消歧 ​

rank 端点若一处含 $i$、一处不含，会让位置逐层漂移。空间须分别计算位向量、rank/select 索引和树结构；不能把“树高约为 $\log \sigma$”写成每一层都恰有 $n$ 位。Huffman-shaped、wavelet matrix 和熵压缩需另写保证。动态更新要维护各层位向量，不由静态结构自动支持。Wavelet tree 与信号处理的小波变换只同名，不做数值基函数分解。

构建与范围计数 ​

按字符全序理路全序Total order · Linear order任意两个元素都可比较的偏序。稳定分割各节点序列，产生位向量的工作为 $O(n(1+\log \sigma ))$；若显式建立整个字母表树，再加 $O(\sigma )$。实际只建非空节点可避免空子树，字母表的坐标压缩与映射仍须另计。

基本指针版本的位向量不超过 $n\lceil {\log }_2\sigma \rceil$ 位，树和节点区间等元数据另占 $O(\sigma \log (n+\sigma ))$ 位；各短位向量的索引头也必须计入，不能只把单张长位串的 $o(n)$ 逐节点照抄。采用统一的位向量编码与索引，可以得到经典上界 $n\lceil {\log }_2\sigma \rceil +o(n)\log \sigma +O(\sigma \log n)$（取已编码、$2\le \sigma \le n$ 的字母表）。进一步改变平衡划分形状，并把各层拼入一个可导航大位串，可以去掉拓扑指针项；这是另一个具体表示方案，不是任意指针树都自带的空间界。

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

区间映射的完整轨迹 ​

图取等价的字符编号 $[1,6]$，原串为 $(3,1,4,1,5,2,6,2)$。完整树各内部节点位向量的长度为 $8,5,3,4,2$，合计 $22$ 位，小于上界 $8\lceil {\log }_{2}6\rceil =24$，也说明它不等于 $8{\log }_{2}6$。

查询原区间 $[1,7)$ 的第三小值，根先映到左区间 $[1,4)$，再映到 $[0,3)$。在字符 $1,2$ 的最后分叉，左边有两个 $1$，所以把 $k=3$ 改成 $k=1$ 进入右叶，返回 $2$；直接排序该区间得到 $(1,1,2,4,5,6)$，核对一致。

在节点位向量 $B$ 上，父区间 $[l,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 的空间与时间结论不能原样复用。