c - 对于间隔上的翻转和状态查询，什么是好的数据结构

Question

我有一个问题，一个男孩有 n 张牌(2 张脸，一张黑一张白 <=> 0/1)。最初，牌面都是白色的。 我需要能够对 n 张卡片的行进行两次操作。

• flip(i,j) 在第 i 行和第 j 行索引之间翻转卡片
• state(i) 返回第 i 个索引位置的卡片颜色

我需要找到一种将这两个操作的总和保持在 O(n) 下的方法。 有什么好的数据结构可以解决这个问题吗？

Answer 1

您可以创建一棵平衡树，其中卡片是叶子，每个节点都有翻转指示器。

要翻转卡片，请翻转最靠近覆盖区间的根的节点。这是 O(log n)。

要获取卡片的状态，请通过根到相应的叶子并对路径中所有节点的翻转指示器进行异或运算。这也是 O(log n)。

例如，如果你有这样的树:

     A
    / \
   /   \
  B     C
 / \   / \
1   2 3   4

并且想要翻转区间 [1, 3]，您将翻转节点 B 和 3。要获得 2 的状态，您将对 A、B 和 2 中的值进行异或，并发现节点已翻转。