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/

You have posted way to much code in your question, which makes it unclear to us (and to future readers) exactly where the problem is. Please reduce your problem code to 10 lines or less. See: How to create a Minimal, Complete, and Verifiable example and How to Debug Small Programs. — Joe C
I am not getting in which part the problem is. I have tested on small arrays and it is working fine but I am unable to figure out where the problem is — Brij Raj Kishore
Then you need to spend some time in a debugger. When you're done that, spend a bit more time. And then after that, even more time. Until you've narrowed your question down to an MCVE, then community is not going to help you. — Joe C
Minimal, Complete and Verifiable Example. In your case, you need to focus on the Minimal bit. — Joe C

Gaurav Gaurav · Accepted Answer · 2017-09-11T08:23:54

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.

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

1 Answers