对于间隔上的翻转和状态查询来说，什么是好的数据结构
我有一个问题，一个男孩有 n 张牌（2 张牌，一张黑一张白<=> 0/1）。最初，卡片都是白色的，面朝上。 我需要能够对 n 张牌的行进行两次操作。
- Flip(i,j) 翻转 i 行和 j 行索引之间的卡片
- state(i) 返回 i 索引位置处卡片的颜色
我需要找到一种方法来将这两个操作的总和保持在 O(n) 以下。 有什么好的数据结构来解决这个问题的想法吗？
I have a problem in which a boy has n cards (2 faces one black one white <=> 0/1). Initially the cards are all white faced up.
I need to be able to do two operations on the row of n cards.
- flip(i,j) flips the cards between rows i and j indexes
- state(i) returns the colour of the card at i index position
What i need to find is a method to keep the sum of these two operations under O(n).
Any ideas of a good data structure to solve this?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
您可以创建一棵平衡树，其中卡片是叶子，并且每个节点都有翻转指示器。
要翻转卡片，请翻转最接近覆盖间隔的根的节点。这是 O(log n)。
要获取卡片的状态，请遍历根到相应的叶子，并对路径中所有节点的翻转指示符进行异或。这也是 O(log n)。
例如，如果您有这样的树：
并且想要翻转区间 [1, 3]，您将翻转节点 B 和 3。要获得 2 的状态，您将对 A、B 和 2 中的值进行异或并找出节点被翻转。
You could create a balanced tree where the cards are leaves and have flip indicator at each node.
To flip the cards, flip the nodes closest to the root that cover the interval. This is O(log n).
To get the state of a card, go though the root to the corresponding leaf and xor the flip indicators from all nodes in the path. This is also O(log n).
For example, if you had tree like this:
And wanted to flip the interval [1, 3], you would flip nodes B and 3. To get the state of 2, you would xor values in A, B and 2 and find out that the node is flipped.