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 | ecnerwala | 3648 |
2 | Benq | 3580 |
3 | orzdevinwang | 3570 |
4 | cnnfls_csy | 3569 |
5 | Geothermal | 3568 |
6 | tourist | 3565 |
7 | maroonrk | 3530 |
8 | Radewoosh | 3520 |
9 | Um_nik | 3481 |
10 | jiangly | 3467 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 174 |
2 | awoo | 164 |
3 | adamant | 163 |
4 | TheScrasse | 159 |
4 | nor | 159 |
6 | maroonrk | 156 |
7 | -is-this-fft- | 150 |
8 | SecondThread | 147 |
9 | orz | 146 |
10 | 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.