What can be the best order of calculating minimum from a given array?

If your answer is <O(n^2),O(1)> this blog is for you. Now using sparse trees it is possible to calculate it in <O(n),O(sqrt(n)) time.

This method is just a simple modification of DP we use brutally. First we will make a DP in linear order dp[i][j] where i-j<sqrt(n).This will store the minimum value from i to j. Then we divide the whole queried range into pieces of length sqrt (n) each. Now for any query like q[i][j] just calculate the minimum of all the subarrays lying completely inside. Now in the worst case you will be left with 2 * (sqrt(n)-1) numbers on both sides. Just calculate them iteratively.

Lets say this is the case. First make the dp in linear time of length sqrt (n)each. Now To caluclate Q(2,7), Calculate all the subarrays lying completely inside. Now we are left with A[2] and A[6], A[7]. Just compare them one by one.

The maximum no of elements we have to compare one by one is always less than 2*[sqrt(n)-1]. The maximum number of blocks of subarray we have to compare will be less than sqrt(n). So we are left with atmost worst case order 3*sqrt(n) .

</Keep Coding>

### Like this:

Like Loading...

*Related*