Is there any video tutorial for the same ?
Not that I know of, but this is a good tutorial for the data structure used here by @nilesh3105: Disjoint Sparse Table
I was just recently readed quite well about SPARSE TABLE OPTIMIZATIONS
In which we first solve the queries regarding the subarrays only of size 2^j where j varies from 0.1…log2(n).
Then for every corresponding subarray size starting from 1.2…4…8…16… we build our SPARSE TABLE in an bottom up dp approach within a O(nlogn) time.
Then for every query we check two things:
- First if the query size is divisible by 2 we can just look up from our sparse table
- otherwise we have to calculate the highest closest power of 2 to our query size by using int j = floor(log2(Ri-Li+1)). And then for the last subarray of size 2^j starting from R-(2^j)+1 till R we check our ans and also for the first subarray from L to (L+(2^j)-1) we find our answer …
Can anyone please tell me that can we apply this approach here as i know this approach works well for the range min, range max, range gcd type queries etc but for the range prod queries how to handle the ans for the 2 subarrays as discussed above when the size of query is not an power of 2.