动态简洁位向量

动态接口与计算模型 ​

维护位串 (B[0\ldots n-1])，接口包括 access、rank、select、insert 和 delete。本文采用 [ \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,2L])。插入使叶超过上界时分裂；删除低于下界时，先向相邻叶借位，借不到再合并。迟滞避免一个位在边界附近反复触发分裂和合并。

一次插入、查询与删除 ​

从 (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”字段，会在全零块或全一块上立即失效。

时间与空间目标 ​

若树高为 (O(\log n/\log\log n))，每个节点能在一个或少数机器字内完成局部前缀选择，就可得到典型的 polylog 更新和查询时间。不同构造在 fanout、叶块编码、随机化与最坏/摊还保证之间取舍，静态位向量的 (O(1)) rank/select 通常不能在支持任意插删后原样保留。

不压缩时，目标是 (n+o(n)) bit 加上必要的全局元数据。零阶压缩版本希望接近 [ nH_0(B)+o(n)\ \text{bit}, ] 其中 (H_0) 只反映 0 与 1 的频率。达到这个式子要求叶块按内容编码，并把树指针、块边界、计数和空闲空间一起纳入冗余分析；仅把叶内容送入压缩器，内部节点仍用大量指针，不构成该空间结论。

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

在动态二元序列或 wavelet tree 的某一层，插入一个字符会转化为位向量中的一次 bit insert。该层在插入位置前的 rank 决定字符进入下一层的坐标，因此更新不是“先插完所有层再计算”：每层都要用更新前的前缀计数确定下一位置，再把本层结构持久地改好。

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

与相邻结构的区别 ​

普通动态数组公理库动态数组Dynamic array · Resizable array以预留容量和偶发整体搬迁支持可变长度的连续序列结构。擅长尾部追加或按位置存取，却没有按 1 的累计数搜索的摘要。Rope 能在大文本上分段插删，但若节点只存字符数，不存 ones，就不能快速回答 rank/select。静态简洁位向量公理库简洁位向量succinct bit vector · rank-select bit vector以 n+o(n) 位表示静态位串，并在 Word-RAM 上常数时间支持 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, 2014.
• Gonzalo Navarro, Compact Data Structures: A Practical Approach, Cambridge University Press, 2016.