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/
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/
Can you tell me your seg tree approach? I was only able to think of a O(n * 32) with 2 pointers.
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
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.
Ya i was about to point that out
You can make 32 rsq bit's trees for each bit to get the and of the range.