data-structures - 反转查询区间内点的颜色

Question

注意:这是算法类(class)作业中的一道题。我不是在寻找解决方案，但可能是我当前方法的一些方向。

问题是:

For the interval [0, 1], each point can be colored either white or black. Initially, all of the points are colored white.

Suggest a data structure that supports the following:

Reverse(x, y): Reverse the color of each point between x and y. A point that was black
becomes white, and vice versa. The color of other points are not effected.

Report(x): Report the color of x.

The operations should both work in O(log(n)) time, where n is the number of reverse operations. Do not use more than O(n) space.

Answer 1

间隔的自平衡搜索树的想法是一个很好的想法。但是，稍微“偷懒”一下，可以省去很多工作。如果需要反转整个子树，只需在子树的根部设置一个标志即可。稍后，当遍历该节点时，您可以将标志传播到树中。

另请注意，添加一个区间应该只需要拆分最多 2 个现有区间，因此树最多 O(n) 个节点，其中 n 是执行的反向操作的数量。

举个例子，假设我们有下面这棵树:

现在我们被要求反转 (.1, .9)。这会影响树中的每个叶节点，但我们最多可以访问 2d 个节点，其中 d 是树的深度。在下图中，我们执行了反转。边框颜色表示发生了什么:

• 蓝色 - 访问过
• 青色 - 分割
• 绿色 - 创建
• 红色 - 标记为反转
• 洋红色 - 实际上是反转的

现在，假设我们被要求报告 3.5 的颜色。我们遍历树，边走边传播反转标志。

如您所见，这两个操作都可以在 O(d) 中完成，其中 d 是树的深度。如果你保持树平衡，这将是 O(log(n))。