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.
We can solve the problem for each bit independently.
Let's assume that we want to compute the contribution of the k-th bit to the answer. If it's set in p, the answer is the number of elements in the range with the value of this bit equal to zero (otherwise, it's the same thing but for the elements with this bit equal to one).
How to count the number of such elements efficiently? We can build a prefix sums array for each bit. This way, we obtain the number of elements with or without the given bit in a range in constant time.