starbot's blog

Spoj Problem ANDROUND
By starbot, history, 8 years ago, In English

Hello !!!

I was wondering about how can we solve this problem using BIT.

I got AC using seg tree but I also saw a comment where someone solved it using BIT.

Help would be appreciated.

Thanks.

Problem :- http://www.spoj.com/problems/ANDROUND/

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you tell me your seg tree approach? I was only able to think of a O(n * 32) with 2 pointers.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Well its a very basic seg tree problem. (nlogn)

    First you need to know that each a[i] will be equal to combined AND (&) of i+k and i-k elements. So all you need to do is build a seg tree in which each node contains AND of the range under it. Then for each array element you need to perform a query from i to i+k and i to i-k and print the ans. Since the array is cyclic you need to see that you don't go over n or below 0. That's it. Its complexity is nlogn.

    Here's my code :- https://pastebin.com/7S9Ez45F

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

There exists a range-update range-query method for fenwick tree: see this

Now fenwick tree becomes exactly like segment tree for this problem.

Edit: My bad. I realised that cumulative bitwise AND of a range cannot be negated like range sum and xor.

→ Reply
»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

You can make 32 rsq bit's trees for each bit to get the and of the range.

→ Reply