动态简洁位向量

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

一次插入、查询与删除 ​

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

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

若随后删除首位，位串变成 $011100$。根到首叶路径上的 len 都减一，ones 也因删去的是 1 而减一。此时 ${\mathrm{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 加上必要的全局元数据。零阶压缩版本希望接近

其中 $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$ 对更新时间的贡献计入，而不能只报告树高。