Блог пользователя coderbond007

How to calculate XOR between each pairs of index of an array?
Автор coderbond007, история, 7 лет назад, По-английски

I was solving this problem. As no editorial is provided for this solution. Can anybody help me to figure out how to calculate XOR between each pairs of integers (i, j) such that 1 ≤ i ≤ j ≤ N?

  • Проголосовать: нравится
  • +12
  • Проголосовать: не нравится

»
7 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

This can be done using segment tree.

You can build segment tree just like we do in case of minimun or maximum function. We can do this because the XOR operation is associative. This can be done in O(n) time.

Querying is same as the standard case with change in binary operation as XOR. This will take O(logn) time.

In case you haven't read about segment tree, you can refer this awesome post.

→ Ответить
  • »
    »
    7 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

    It's not a good idea. You don't need a segment tree if you have no modification queries and function that you want to calculate is invertible. In case of calcing sum, multiplication by prime modulo, xor, etc. you should just calculate prefix sums.

    UPD. Because of the previous comment I thought that problem is about calculating xor in range, but it is not so.

    → Ответить
  • »
    »
    7 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    But this problem is not asking to calculate xor in range(Did I misunderstood something?)

    → Ответить
»
7 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

We can use prefix xors + trie + dp to solve this.

we can break l to r as less than x .And calculate l to r = (less than r) minus (less than l).

Similar to problem 3 here.

PS: I would be happy to know how to solve by segment trees or anyother way

→ Ответить