Flip Cards

Question

There is an array of n cards. Each card is putted face down on table. You have 2 queries:

  1. T(i, j) - turn cards from index i to index j(include i, j)
  2. Q(i) - 0 if card if face down else 1

Thoughts

array

如果用普通array实现的话，

  1. T(i, j) - O(n)
  2. Q(i) - O(1)

BIT

The array f[] holds information on how many times a card has been flipped. That is, card i has been flipped (f[1] + f[2] + ... + f[i]) times.

In this case:

  1. T(i, j)

Now if we want to flip the cards from i to j

  • for each k between i and j, (f[1] + f[2] + ... + f[k]) must be increased by 1. This is done by increasing f[i] by 1
  • for each k between j + 1 and n, (f[1] + f[2] + ... + f[k]) must remain the same, this is done by decreasing f[j+1] by 1.

operations:

  • update(i, 1)
  • update(j+1, -1)

time: O(logMaxVal)

  1. Q(i)

这里的Q(i)就相当于在读i的cumulative freq,因为我们定义f[1] + f[2] + ... + f[i] 表示i被flip的次数，然后module 2就可以知道结果了。

operations:

  • return read(i) % 2

time: O(log MaxVal)

总结

这里这样特殊的定义方式使我们能够用BIT，因为f[1] + f[2] + ... f[k]表示k被flip的次数， 所以我们将update和read都变成了log。

使用BIT我们感兴趣的是cumulative frequency, tree里面跟多表示的也是cumulative value, 所以我们要把思维转变到这上面来。

Solution

Reference