For a given array of integers, we have to calculate XORed
sum withing a given range [L, R]
, by XORed
sum I mean Σ(Arr[i]^p)
where i:[L,R]
and p
is some number. This can be easily done while calculating the XORed
sum till every i-th
element in array from beginning of the array. Now the problem occures when the p
changes very frequently. And recalculating XORed
sum till every i-th
element does not seems to be an ideal solution in this case. I guess this can be done using fenwick
tree or BIT
. But I am not able to figure out how to proceed with fenwick
tree or BIT
. Any help would be appreciated.
It’s the same as using BIT for sum, just replace + with ^ (xor).
Could you provide the problem source? I am not comfortable providing you with an answer otherwise.
2 Likes