Problem
In the above problem, they asked to calculate pairwise XOR, OR, AND op. taken one at a time under a certain range [l,r] . My question is how to tackle such problems when you have to calculate n chose 2 distinct ops and calculate them.
1 Like
Here the idea is to maintain a segment tree that will store the count of every bit in that range , i.e
It will maintain an array( of size 30 say ) whose ith element will store the count of numbers whose ith bit is on in that range. Now update operations are simple as u just modify the bitwise count, and for query u know only the ith bit will interact with the ith bit so u use some simple math ( which i want you to try yourself ) and after that the net sum would be sum over all i (count[i]*1<<i)