@soumik33
See here,we precompute the prefix product for all indices which are divisible by 2^k where k=1…logN
So
We calulate prefix product for all subarrays from prevPivot+1 to currPrivot-1. And prefix product from currPivot to nextpivot - 1
So lets say for k=2:
Indices:4,8,12,16,20,…
So we calculate for following ranges:
(1,3),(2,3),(3,3)
(4,4),(4,5),(4,6),(4,7)
(5,7),(6,7),(7,7)
(8,8),(8,9),(8,10),(8,11)
We do this for k=1…logN
Now suppose a query:
1-6
(Here pivot are 2,4)
So it can be (1-1)(2-3)(4-6)
(Here pivot is 4)
Or (1-3)*(4-6)
The second one takes only 1 multiplication
Consider another eg:
Range 17:22
So (17:19)*(20:22)
Since we have precalculated for these results for all multiples of power of 2 it can be done in O(1).
#note 20=4 * 5=(2^2)*5
So it means we have to choose such a number in the range which is multiple of some 2^k and k is maximum(as if not we have to do more than 1 multiplication)
So lets express 17:0b10001
22:10110
Exor result=111
So last set bit is 2
So pivot is multiple of 2^2
(Also note that there is only 1 multiple x for x*2^k as for x-1 it is less than L and for x+1 it is greater than R)
Proof for xor:
See @hemanth_1 comment.Really nice explaination.
Hope this helps.
Plz correct me if i am wrong.