用于表示两个值的数据结构，具有三种操作

Question

我们假设有n个值。所有的值都是false，可以被更改为true。

我想对这些值执行3个操作，并且它们具有特定的时间复杂度：

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

我实际上不太关心空间复杂度。该结构在开始时使用固定长度进行初始化。初始化需要多长时间并不重要。

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

- Diet

---

你忘记指定空间复杂度了。 - Zabuzard

@Diet - 看起来这是一个相当困难的问题，你知道这种结构实际上是否存在或者可能的正确答案是：“这种结构不能存在”吗？ - libik

结构在开始时以固定长度初始化。初始化所需的时间并不重要。 - Diet

@libik - 我相信它可以存在，只是我找不到标准结构的正确组合/修改。 - Diet

“find”和“change”在“O(1)”（平摊）中一起实现真的很难。为了实现“find”，您需要某种排序方式。但是，由于“change”，在排序结构中进行插入会再次产生“log n”，因为您需要找到正确的插入位置，这肯定不是“O(1)”。 - Zabuzard

Answer 1

在 [0, n) 上建立一个 线段树，对于每个基本区间 [i 2^k, (i+1) 2^k)，存储该区间中布尔值的 AND。

因为它只是一个数组查找，所以val(i)是常数时间。

如果我们修改传统的自顶向下传播算法，可以将change(i)的摊销时间降至常数时间，方法是在特定层级上，如果没有更改，则提前退出。这是因为在任何时候，从距离根节点k级的区间中写入的次数最多是从距离根节点k+1级的区间中写入次数的一半（通过对k进行归纳来证明）。

可以按照以下方式在对数时间内实现find(i)。首先观察到，仅需找到最近的左邻居和最近的右邻居，并取两者中更近的一个。要找到位置i的最近虚假右邻居，请将[i, n)分解成基本区间。找到最左侧包含一个虚假的区间（即其AND是false）。从该区间向叶子节点移动，每层检查左半部分是否为false。如果是，则向其下降；否则，使用右半部分。

在单位成本RAM上（即真实硬件的理论版本），通过将树的扇出从2更改为字长（Theta(log n)）并使用位操作，可以使find(i)的时间降至O(log n / log log n)，存储单元数为O(n / log n)。

- David Eisenstat

Answer 2

使用哈希映射和二叉搜索树的组合。

例如- 假设 boolean[] A = {false, false, false, false}

创建哈希映射（键为整数，值为对象）

遍历每个项目： 1. 创建具有索引和值作为属性的对象。 2. 将对象添加到映射中。 3. 使用对象的索引将相同的对象添加到BST中以用于BST中的位置。

现在执行以下操作：

1. Val(i)：直接获取对象并返回对象的值。复杂度（1）

2. Change(i, true/false)：再次从映射中获取对象并更新其值。复杂度O(1)

3. Find(i)：检查该映射中对象的值是否为false。如果是false，则返回；否则，在BST中进行遍历以检查最近的索引是否具有值为false的对象。请注意，基于对象键的BST遍历可以在O(logn)中完成。因此，复杂度为O(logn)

- Rahul

---

如何在二叉搜索树中进行遍历以检查最近的索引，其值为false？您没有在更改中更新BST。 - David Eisenstat

@DavidEisenstat，这就是为什么我使用了对象。同一个对象既在映射的值中，也在BST节点中。抱歉，我创建了键为整数，值为布尔值的映射。它的值应该是对象而不是布尔值。 - Rahul

@DavidEisenstat，这就是为什么我选择了对象而不是布尔值。该对象在映射和BST中都存在。因此，在一个地方更新该对象将同时更改另一个地方。抱歉，我使用了键为整数和值为对象的映射。它应该具有对象值。希望这能够解决您的疑虑。 - Rahul

Find(i)如何快速搜索大量的真值？ - David Eisenstat

这就是二叉搜索树的美妙之处。在二叉搜索树中进行搜索的时间复杂度为O(logn)。 - Rahul

搜索是可以的，但你现在尝试的是在值上进行筛选而不是搜索。 - David Eisenstat