algorithm - 表示具有 3 个操作的二值数组的数据结构

Question

让我们有 n 个值。所有值为 false 并且可以更改为 true。我想要对这些具有一定时间复杂度的值进行 3 次操作:

• val(i) -> 返回索引 i 处的值。时间复杂度 - O(1)。
• change(i) -> 将索引 i 处的值更改为 true。时间复杂度 -摊销 O(1)。
• find(i) -> 返回最接近索引 i 的索引，它包含值false(如果i上有false，则返回i)。时间复杂度 - O(log n)。

我真的不关心空间复杂度。该结构在开始时以固定长度初始化。初始化需要多少时间并不重要。

用于这些操作的数据结构应该是什么样的？

Answer 1

设置 segment tree在 [0, n) 上，并且对于每个基本区间 [i 2^k, (i+1) 2^k)，存储该区间中 bool 值的 AND。

val(i) 是恒定时间的，因为它只是一个数组查找。

change(i) 如果我们将通常的向根传播算法更改为在特定级别没有变化的情况下提前退出，则将在恒定时间内摊销。这是因为在任何给定时间，从根开始写入间隔 k 层的次数至多是从根开始写入间隔 k+1 层的次数的一半(通过对 k 的归纳来证明这一点)。

find(i) 可以按如下方式在对数时间内实现。首先观察，找到最近的假左邻居和最近的假右邻居就足够了，取两者中较近的一个。要找到位置 i 最近的伪右邻，将 [i, n) 分解为基本区间。找出这些区间中最左边包含假的(即它的 AND 为假)。从这个间隔开始向叶方向前进，检查每一层左半部分是否有错误。如果是，就下降到它；否则，使用右半边。

在单位成本 RAM(即实际硬件的理论版本)上，我们可以将 find(i) 缩短到 O(log n/log log n) 通过将树扇出从 2 更改为字大小 (Theta(log n)) 并使用按位运算。