I need help with BIT version of the solution. I get it how update is done. But divide part is causing problem for me.
Here are my doubts : (consider the BIT storing index divisible by 2)
Finding sum upto l-1. Isn’t it the number of elements in array divisible by 2 occurring before l-1 (inclusive)? If so, what is the purpose of it?
How is the next index greater than present sum found? If we search each and every elements won’t it be linear?
Is the approach by tester and setter different than the one described in the editorial?
At the end there is another approach that uses prefix sum to find number of times a given element will be divisible by p. Won’t this affect the updation query? I mean suppose at index i value in array is 50. Let’s say there are 3 division operations for this index. Then let the value changes to 16. If we compute the division at the end, (after finding the prefix sum), there are three divisions for 50, not 16. Dividing 16 by 2 three times will result in incorrect answer. How is this problem handled?