简洁数据结构

Succinct 不只是“占用线性空间”，而是相对对象族的信息下界只多低阶冗余。编码负责区分所有对象，索引再把可导航的局部摘要压进低阶空间；若查询仍需完整解压，或每个节点保留普通指针，便失去了这项接口保证。

模型边界 ​

$O(n)$ bits 不一定 succinct，必须相对下界。共享查表是否计空间、字长 $w=\mathrm{\Theta }(\log n)$ 与查询时间都要声明。动态更新常需更多冗余，不能把静态常数查询直接搬入动态版。

Compact、succinct 与 compressed 也不同：压缩结构可按实例熵使用更少空间，succinct 以对象族最坏信息下界为基准；self-index 还要求不保存原文也能定位内容。三者可能重叠，但不是同义标签。

有序树的括号编码全过程 ​

DFS 进入节点输出 (，离开输出 )。根带两个叶的树编码为 (()())；扫描任意前缀时 excess=左括号数减右括号数非负，末尾归零。节点的开括号位置代表节点，匹配右括号界定其整个子树区间。

父节点可由前一个 excess 更小的位置恢复，第一个孩子是紧随开括号的下一开括号，下一兄弟在匹配右括号之后。支持这些操作需要 rank/select、find-close 与 excess 搜索索引；主体 2n bits 之外的辅助结构必须合计 $o(n)$ 才保持 succinct。

信息下界的核对 ​

$n$ 节点有序树数为 Catalan $C_n$，Stirling 近似给 ${\log }_2{C}_n=2n-\mathrm{\Theta }(\log n)$。因此 2n 括号主项距最优仅低阶。若换成无序树或带标签树，对象族大小改变，下界也改变，不能继续以 2n 宣称 succinct。

查询时间与全局表 ​

Word-RAM公理库Word-RAM 模型Word RAM · Word-RAM model以 w 位机器字、常数时间随机访存和明确字级操作集分析算法的随机访问机模型。 常数操作假设 $w=\mathrm{\Theta }(\log n)$。微块表若对所有实例共享，表大小可为 $o(n)$；若每个实例重复存一份仍要计入。导航返回节点序号还是括号位置也需接口转换。

与压缩、自索引、动态结构对照 ​

Entropy-compressed 结构按具体数据分布/零阶熵缩小，succinct 按对象族最坏下界；self-index 还能从索引恢复原对象。动态插入括号会移动后缀位置并修改 excess，静态常数查询不自动支持更新，通常要付对数时间或更多冗余。