coderbond007's blog

How to calculate XOR between each pairs of index of an array?
By coderbond007, history, 7 years ago, In English

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?

  • Vote: I like it
  • +12
  • Vote: I do not like it

»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply