Улучшение сложности метода обновления в минимальном запросе по дальности с использованием метода декомпозиции квадратного корня

Question

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

Я пытаюсь решить этот вопрос. Я делаю векторный размер Math.ceil(Math.sqrt(arrSize)). Я использовал следующие методы - Для построения вектора sqrt

Я беру куски квадратного корня и нахожу наименьший индекс в блоке и сохраняю их в массиве vect.

Как я могу улучшить мою сложность запроса на обновление из 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;

}

использовал этот учебник -: http://www.geeksforgeeks.org/sqrt-square-root-decomposition-technique-set-1-introduction/

Answer 1

Если вам нужно улучшить сложность, вы должны использовать деревья сегментов. В этом случае вы не можете напрямую обновить индекс массива vect, как в случае запроса суммы диапазона. Вы должны снова найти минимум блока.