表示包含3个操作的二值数组的数据结构

Question

让我们看看n值。所有值都是false，可以更改为true。我想对这些具有一定时间复杂性的值进行3次运算：

• val（i）-

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

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

Answer 1

使用hashmap和二进制搜索树的组合。

假设布尔值[]A={false， false， false， false}

创建hashmap（key为整数，value为Object）

迭代每个项目：1.以index和value作为属性创建对象。2.将对象添加到地图。3.使用BST中位置的对象索引将相同的对象添加到BST。

现在执行以下操作：

>

更改（i， true/false）：再次从map获取对象并更新其值。

查找（i）：检查该地图中对象的值是否为假。如果为false，则返回，否则在BST中进行遍历，以检查值为false的最近索引。注：基于对象密钥的BST遍历可以在O（logn）中完成。因此复杂性O（logn）

Answer 2

在[0，n]上建立一个段树，对于每个基本间隔[i 2^k，（i 1）2^k），存储该间隔中布尔值的and。

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

change（i）如果我们改变通常的向根传播算法，使其在特定级别没有变化的情况下提前退出，则按固定时间摊销。这是因为在任何给定的时间，从根到间隔k级别的写入次数最多是从根到间隔k 1级别的写入次数的一半（通过对k的归纳来证明这一点）。

find（i）可以在对数时间内实现，如下所示。首先观察，找到最近的假左邻居和最近的假右邻居就足够了，然后取两者中较近的一个。要为位置i查找最近的假右邻居，将[i，n）分解为基本区间。找出这些区间中最左边包含假的区间（即its和is false）。从该区间开始，向前看，检查每一级的左半部分是否有假。如果有，向下看；否则，使用右半部分。

在单位成本RAM（即实际硬件的理论版本）上，我们可以通过将树扇出从2更改为字长（Theta（logn））并使用位操作，获得O（n/logn）存储字的find（i）时间O（logn/logn）时间。