java - 使用平方根分解技术提高范围最小查询中更新方法的复杂度

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 数组的索引。您必须再次找到该块的最小值。