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.
Could you provide the problem source? I am not comfortable providing you with an answer otherwise.
2 Likes
It’s the same as using BIT for sum, just replace + with ^ (xor).