ransel - 一个 succinct rank/select 数据结构的库

Succinct 数据结构提供了一种空间高效的方式来存储位图（或根据你的观点是整数集合）。它们使用基于两个基本函数的简单但强大的 API

• rank，它接受来自集合域的元素 x，并返回小于 x 的集合元素的数量。
• select，它接受来自集合范围的索引 i，并返回集合中的第 i 个最小元素。

存在许多衍生操作，但它们都可以用 rank 和 select 来表示。然而，在某些情况下，我们确实使用了特殊的实现，这些实现可能比原始实现具有更好的运行时性能。

lib.rs:

ransel 库提供了由 Guy Jacobson 提出的整数集合的 rank/select API

Jacobson, G., 1989, 十月. 空间高效静态树和图。在 30 届计算机科学基础研讨会（第 549-554 页）。IEEE 计算机协会。

rank/select API 的美妙之处在于，它允许在整数集合（或根据你的观点是位图）上执行许多有用的操作，而无需考虑集合的底层表示。事实上，根据集合的预期密度和大小，可以使用许多不同的表示。

已经提出了这种 API 的各种形式（特别是 Simon Gog 的 sdsl-lite），定义略有不同。我们使用的定义是统一基于 0 的。

给定一个包含非负整数的集合 S，我们定义

S.size() 是域的大小，并且至少比 S 中的最大元素大 1。

S.count() 是 S 中的元素数量。

S.rank(x) 表示集合 S 中严格小于 x 的元素数量。 rank_1 是一个别名，而 rank_0 是其互补定义：小于 x 的非负整数中不在 S 中的元素数量（请注意，rank_0 和 rank_1 可以用彼此来定义，即 S.rank_0(x) = x - S.rank_1(x)）。

S.select(i) 是集合 S 中第 i 个最小的元素，其中 0 是第一个元素的索引。

API 被分解成组件

ImpliedSet 特性公开了 size 和 count 操作。

Rank 特性公开了 rank 和其相关操作。

Select 特性公开了 select 和其相关操作。