把0和1放进整数数组，可以做前缀计数，但“数组长度是n”不等于“占n位空间”。简洁数据结构要求先确定信息下界，再计算索引冗余；指针、绝对计数和查找表都不能从空间账本中消失。

本篇实现静态位向量的rank/select接口，用Python参照和C++固定字长实现核对查询。教学实现采用简单分块索引，明确不把它称为已经实现n+o(n)位的succinct结构。

一种查询数个数，另一种查询找位置

输入为长度n的二进制序列B，元素只能为整数0或1，构造后不再修改。rank1(i)返回半开前缀B[0:i]中1的数量，0≤i≤n；select1(k)返回第k个1的零基位置，k从1开始，沿用00与06篇的顺序统计约定。

空序列可以构造，rank1(0)=0，但任何select都越界。全零序列也没有合法select。非法位值拒绝，rank端点或select序号越界拒绝，不用某个特殊位置冒充答案。

例如B=[0,1,0,1,1]，rank1(3)=1，select1(2)=3。这里rank参数是位置端点，select参数是出现序号；若p=select1(k)，则rank1(p)=k−1、rank1(p+1)=k，不能误写成rank1(p)=k。

64位分块的最小索引

每64个位打包成一个字，序列较前的位置放在较低位。prefix[b]记录第b块之前的1数量，prefix[0]=0，最后一项是总1数。末块不足64位的高位保持0。

查询rank1(i)时，令b=i//64、r=i%64。答案为prefix[b]加上第b块最低r位的popcount；r=0时只读prefix[b]，不读可能越界的下一块。因此n恰好是64倍数时，rank1(n)仍合法。

在C++中不能计算1ULL << 64后再减1，这种移位超出类型宽度。实现把整块边界作为单独分支，只有0<r<64才建立低位掩码。Python大整数允许更宽的移位，不代表照抄到固定字长语言仍正确。

select1(k)先在非递减prefix里找第一个计数至少为k的块末边界，再进入其前一块。减去该块之前的1数量，得到块内出现序号，扫描至多64个位返回位置。即使中间有全零块、prefix出现重复值，第一次达到k的边界仍定位到包含第k个1的块。

不变量足以解释两个查询

打包不变量是第b块的第r位恰等于B[64b+r]，合法范围外为0。prefix由前一项加当前块popcount得到，所以归纳可知它恰好计入所有更早的块。

rank把目标前缀分成完整块与最后一个块内前缀，两部分互不重叠且覆盖全部位置，计数相加就是答案。select先用prefix排除更早块，再在唯一目标块内按位次扫描；每遇到一个1把剩余序号减1，归零时正是所需出现位置。

查询只读，不会使索引过期。若直接修改words却不重算后面的prefix，后续块的rank和select都可能错误。动态位向量是另一个数据结构问题，不能在静态接口上直接加一个位写入就继续沿用证明。

操作次数与空间逐项记账

记块数b=⌈n/64⌉。构造扫描n个位并累计b个块，耗O(n+b)次基本操作。固定字读、popcount与计数算术按常数成本时，rank为O(1)，select为O(log(b+1)+64)；本实现没有常数时间select索引。

以上查询界均为确定性的最坏操作次数界，不依赖随机输入，不是期望或高概率界。动态扩容的构造成本按数组摊还规则计算，不影响构造完成后只读查询的最坏界。

Python每块限制在64位以内，但prefix值与下标还涉及大整数成本，不能把任意长度Python整数的bit_count说成常数时间。C++使用明确的uint64_t类型，n与计数必须落在可表示、可分配范围内；这里核对的是有限机器模型，不是无限规模机器。

保存位数据需要64b位，另有b+1个绝对前缀计数。实际C++每个计数64位，这部分约与原位数据同量级，冗余不是随n增长而趋于零的比例。若在允许n继续增长的抽象模型里让每个计数占Θ(log n)位，固定64位分块的计数总量为Θ((n/64)log n)，更不能说是o(n)。

Python列表、整数对象和引用还会增加空间。对象计量必须明确是否包括实例、输入、解释器分配器及共享整数；按对象身份去重可以避免把同一个小整数对象重复相加，却不能把局部getsizeof总和当作进程RSS。

真正的succinct还缺什么

所有长度n的二进制串共有2ⁿ种，因此一般无损表示至少需要n位。succinct要求n+o(n)位，compact只要求与信息下界同阶；两种词不应因为中文都译作“紧凑”而混用。

MIT讲义的静态rank方案使用随n变化的两级目录：大块存全局计数，小块存块内计数，最后用小模式查找表回答局部问题。目录字段范围不同，因而不用为每个小块都支付log n位。表的所有条目也计入o(n)辅助空间，不能把预计算当成免费外存。

select不能只套rank的固定长度分块。讲义按1的出现数量分组，把跨度很大的稀疏组单独处理，再细分短组并使用查找表。它借助稀疏与稠密情形的不同计费方式，实现常数查询与次线性冗余。

这些界要求字RAM模型：字长足以寻址，字读取、指定字操作与表查询视为常数成本。它们是讲义方案的结论，不是本文64位块加绝对prefix程序的结论。

从位序列走向字符索引

Wavelet tree把字符表逐层分成两半，每层位向量记录字符进入哪一半。查询字符a在前缀中的出现次数时，a决定下降方向，当前前缀长度i用该层rank0(i)或rank1(i)转换成下一层的前缀长度；到达叶子后，长度就是计数。

对于大小为σ的字符表，平衡划分的高度为⌈log₂σ⌉，每层常数时间rank给出O(log σ)查询。这个关系说明位向量索引怎样组成字符索引；本文只实现位向量，不把它计为已经完成wavelet tree或wavelet matrix。作者论文第2节给出了树的导航关系，后续矩阵变体另有布局规则。

可复跑的两种语言证据

从仓库根目录运行：

1
2
3
python3 examples/advanced-algorithms/check_bit_rank_select.py
clang++ -std=c++20 -O2 -Wall -Wextra -pedantic examples/advanced-algorithms/bit_rank_select.cpp -o /tmp/advanced-bit-rank-select
/tmp/advanced-bit-rank-select

本次C++使用Apple clang 21.0.0，目标arm64-apple-darwin27.0.0；独立捕获的运行退出码为0，标准错误为空。两种实现分别检查长度0至10的全部2047个位串，包含20481次rank和9217次select查询，并覆盖63、64、65、127、128、129位的块边界。Python另外运行100个固定种子随机输入；参照直接数原序列中的1或列举其位置。

长度129的样例中，C++两段vector容量的元素载荷为56字节，不含vector对象、分配器与输入。Python按对象身份去重的两个列表及整数元素合计356字节，不含实例与输入。这两个计量口径不同，不能直接计算整个程序的空间缩减比例，更不是RSS或运行速度比较。

有限查询检查核对实现与接口，不证明所有规模下的位空间定理。C++与Python返回相同位置，只能说明相同输入上的语义一致，不能据此把解释器对象布局等同于压缩位数组。

练习

  1. B=[1,0,0,1]时列出全部合法rank1与select1结果，验证rank1(select1(k)+1)=k。解释为什么不加1时结果少一次出现。
  2. 每64位存一个绝对计数，与每个小块只存大块内部计数有什么空间差别？写出各自字段需要表示的最大值，再解释为什么固定常数块长不能自动给出o(n)冗余。

参考资料