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 | 4009 |
2 | jiangly | 3839 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | Geothermal | 3569 |
7 | cnnfls_csy | 3569 |
9 | ecnerwala | 3494 |
10 | Um_nik | 3396 |
# | User | Contrib. |
---|---|---|
1 | Um_nik | 164 |
2 | maomao90 | 160 |
3 | -is-this-fft- | 159 |
4 | atcoder_official | 158 |
4 | awoo | 158 |
4 | cry | 158 |
7 | adamant | 155 |
8 | nor | 154 |
9 | TheScrasse | 153 |
10 | maroonrk | 152 |
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.