动态简洁位向量 | Codeboy's Blog

形式陈述

动态接口与计算模型

维护位串 $B[0..n)$ ，在rank/select 接口上增加位置插入和删除。access/delete 要求 $0\le i<n$ ，insert 在位置 $0\le i\le n$ 之前加入给定位，rank 允许 $0\le i\le n$ ；不存在的 select 序号返回空标记。本文采用

\operatorname{rank}_1(i)=\sum_{0\le j<i}B[j]

的半开区间定义； $\operatorname{select}_1(k)$ 返回第 $k$ 个 1 的零基位置，其中 $k$ 从 1 开始。固定约定能避免插入点附近最常见的一位偏差。

分析通常在 word-RAM 上进行，字长 $w=\Omega(\log n)$ 。一项结果必须同时说明查询时间、更新时间、主数据空间、冗余项以及是否压缩；只写“polylog 时间、succinct 空间”无法判断它是否真的优于普通动态数组。

分块平衡树

一个直接而可扩展的结构是把位串切成叶块，再用平衡多叉树按次序组织。每个内部节点为每个孩子保存两项摘要：

len：该子树包含多少 bit；
ones：该子树包含多少个 1。

access 或 insert 的位置查询按 len 做前缀选择。rank 沿同一路径累加所有已越过孩子的 ones。select 则反过来按 ones 找到包含第 $k$ 个 1 的孩子，并把越过孩子的 len 加到答案位置。叶内用机器字、查表或小型压缩块完成局部操作。

叶块可以用有余量的阈值避免反复重建。例如固定整数 $L\ge2$ ，至少有两个叶块时，将每块长度维持在 $[L,4L]$ ：溢出到 $4L+1$ 时均分，两个新块都约为 $2L$ ；下溢到 $L-1$ 时，若相邻块大于 $2L$ ，就把两块内容重新均分，否则合并为一个长度在 $[2L-1,3L-1]$ 内的块。这样，新块与下一次阈值之间留有 $\Omega(L)$ 的余量。仅剩一个块时允许长度从 $0$ 到 $4L$ ；端点块下溢时使用其唯一的相邻块。

较窄的 $[L,2L]$ 也能作为普通平衡树的容量约束，但分裂后的块可能刚好为 $L$ ，一次删除就会再次下溢，不能据此声称已有迟滞。图右展示的正是这种普通分裂；它不承担上述更新间隔保证。

直觉

动态位向量同时有两套坐标：按长度定位第几个 bit，按 ones 计数定位第几个 1。平衡树在每个子树保存这两种质量，便可用同一条下降路径分别完成位置选择和 occurrence 选择；叶块的迟滞则把局部搬移与树重平衡限制在可收费的范围内。

动态简洁位向量在分块树中同时维护长度与一计数并分裂溢出叶 — 长度与一计数、查询路径及叶分裂

例子与边界

一次插入、查询与删除

从 $B=101100$ 开始，在位置 2 前插入 1，得到

10\mathbin{\color{#c33}{1}}1100=1011100.

新串前五位是 $10111$ ，所以 $\operatorname{rank}_1(5)=4$ ；第 3 个 1 位于零基位置 3，因此 $\operatorname{select}_1(3)=3$ 。

若随后删除首位，位串变成 $011100$ 。根到首叶路径上的 len 都减一，ones 也因删去的是 1 而减一。此时 $\operatorname{rank}_1(4)=3$ ，第 3 个 1 位于位置 3。更新摘要必须发生在结构重平衡之后所对应的实际孩子上，否则分裂后的计数会挂在旧节点。

这个短轨迹也说明 position 与 occurrence 是两种不同的搜索坐标。insert/delete 依据 len 定位，select 依据 ones 定位；把两者共用一个未经标注的“size”字段，会在全零块或全一块上立即失效。

时间与空间目标

树高只决定访问多少个节点，节点内的前缀计数、选择和更新也要计费。若一个节点有多对数个孩子，每个计数又占 $\Theta(\log n)$ 位，就不能把全部计数说成装在少数机器字内；快速构造需要专门的动态部分和与紧凑小块技术。叶内插删还可能移动或重编码 $\Theta(L)$ 位，分裂、合并和长度尺度变化也必须纳入成本。

Navarro–Nekrich 的动态序列表示给出如下具体保证。专门取二元字母表、标准 $w=\Theta(\log n)$ 的 word-RAM，并固定 $0<\varepsilon<1$ ，其空间为 $nH_0(B)+O(n/\log^{1-\varepsilon}n)$ 位；access、rank、select 为 $O(\log n/\log\log n)$ 最坏时间，插入、删除为同阶摊还时间。这里是该具体构造的定理，包含其分块、部分和与参数调整，不是仅由上面的树形骨架推出；小规模串另行直接处理。

按全部长度 $n$ 的位串族计量，其信息论下界为 $n$ 位；总存储达到 $n+o(n)$ 位，就满足简洁数据结构在动态位串上的要求。全局元数据也应计入这项总成本。零阶压缩版本希望接近

nH_0(B)+o(n)\ \text{bit},

其中 $H_0$ 只反映 0 与 1 的频率。达到这个式子要求叶块按内容编码，并把树指针、块边界、计数和空闲空间一起纳入冗余分析；仅把叶内容送入压缩器，内部节点仍用大量指针，不构成该空间结论。即使块长有上述迟滞，若每块固定预留 $4L$ 位，空洞仍可能是 $\Theta(n)$ 位；要达到低阶冗余，还须紧凑分配并核算这些未使用位置。

推论与应用

动态文本索引中的状态传播

在动态二元序列或 wavelet tree 的某一层，插入一个字符会转化为位向量中的一次 bit insert。该层在插入位置前的 rank 决定字符进入下一层的坐标，因此应逐层确定分支和下一层位置。在位置 $i$ 插入或删除一位并不改变半开前缀 $B[0..i)$ ，所需 rank 可以在本层修改前或修改后读取；删除时必须先保留原来的位值，以免误用移动到位置 $i$ 的下一位来选择分支。

删除沿相同路径传播。若某个叶块因删除而合并，逻辑位序必须保持不变，父节点的 len/ones 也要反映合并后的单个孩子。局部编码可以变化，但 access、rank 和 select 观察到的序列不能变化，这就是重平衡的语义不变量。

与相邻结构的区别

普通动态数组擅长尾部追加或按位置存取，却没有按 1 的累计数搜索的摘要。Rope 能在大文本上分段插删，但若节点只存字符数，不存 ones，就不能快速回答 rank/select。静态简洁位向量可为固定串建立更激进的常数时间索引，代价是插入会让后缀位置和索引整体失效。

压缩动态位向量也不是完整的动态全文索引。后者还需在多层序列、采样后缀位置和字符字母表之间维持一致坐标；本结构只提供其中可组合的一层接口。

边界与报告规范

全零位串使 select-one 无定义，全一位串则使零阶熵为 0，但仍要保存长度和支持位置更新。这两个极端会暴露“熵空间等于不占空间”的错误表述。API 应明确越界查询是报错、返回哨兵，还是只对有效 $k$ 定义。

并发读写、持久化和崩溃恢复不包含在经典 word-RAM 结果中。工程实现若给叶预留大量空洞来降低搬移成本，应把这部分计入空间；若每次更新重编码整块，也应把 $L$ 对更新时间的贡献计入，而不能只报告树高。

参考资料

Rajeev Raman, Venkatesh Raman and S. Srinivasa Rao, Succinct Indexable Dictionaries with Applications to Encoding k-ary Trees, Prefix Sums and Multisets, ACM Transactions on Algorithms, 2007.
Gonzalo Navarro and Yakov Nekrich, Optimal Dynamic Sequence Representations, SIAM Journal on Computing 43(5), 2014, pp. 1781–1806；作者稿，§§4–7 与 Theorem 2：查询最坏时间、更新摊还时间和压缩空间；§8 的全最坏时间变体具有不同操作界。
Gonzalo Navarro, Compact Data Structures: A Practical Approach, Cambridge University Press, 2016.

形式陈述 ​

动态接口与计算模型 ​

分块平衡树 ​

一次插入、查询与删除 ​

时间与空间目标 ​

动态文本索引中的状态传播 ​

与相邻结构的区别 ​

边界与报告规范 ​

反向链接