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/
# | User | Rating |
---|---|---|
1 | tourist | 3690 |
2 | jiangly | 3647 |
3 | Benq | 3581 |
4 | orzdevinwang | 3570 |
5 | Geothermal | 3569 |
5 | cnnfls_csy | 3569 |
7 | Radewoosh | 3509 |
8 | ecnerwala | 3486 |
9 | jqdai0815 | 3474 |
10 | gyh20 | 3447 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 174 |
2 | awoo | 165 |
3 | adamant | 161 |
4 | TheScrasse | 160 |
5 | nor | 158 |
6 | maroonrk | 156 |
7 | -is-this-fft- | 152 |
8 | orz | 146 |
9 | SecondThread | 145 |
9 | pajenegod | 145 |
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/
Name |
---|
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.