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

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

i trying solve question. making vector size of math.ceil(math.sqrt(arrsize)). have used following methods - constructing sqrt vector

i taking square root chunks , finding smallest index in block , storing them in vect array.

how can improve update query complexity 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 = inindex; < finalindex && < arr.length; ++i) {         if(arr[i] < min) {             min = arr[i];             in = i;         }     }     vect[index/len] = in;  } 

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

if have improve complexity have use segment trees. in case cannot directly update index of vect array in case of range sum query. have find again minimum of block.