Improve the complexity of Update method in Range Minimum Query Using Square Root Decomposition Technique

Question

https://www.hackerearth.com/practice/data-structures/advanced-data-structures/segment-trees/practice-problems/algorithm/range-minimum-query/description/

I am trying to solve this question. I am making the vector size of Math.ceil(Math.sqrt(arrSize)). I have used the following methods - For constructing sqrt vector

I am taking square root chunks and finding the smallest index in the block and storing them in the vect array.

How can I improve my update query complexity from Sqrt(n).

static void update(int[] arr, int[] vect, int index, int elem) {
    arr[index] = elem;
    int len = vect.length;
    int inIndex = ((index / len) * len);
    int finalIndex = inIndex+len;
    int min = Integer.MAX_VALUE;
    int in = -1;
    for(int i = inIndex; i < finalIndex && i < arr.length; ++i) {
        if(arr[i] < min) {
            min = arr[i];
            in = i;
        }
    }
    vect[index/len] = in;

}

used this tutorial -: http://www.geeksforgeeks.org/sqrt-square-root-decomposition-technique-set-1-introduction/

Answer 1

If you have to improve complexity you have to use Segment Trees. In this case you cannot directly update the index of the vect array like in case of range sum query. You have to find again the minimum of the block.