使用平方根分解技术改进范围最小查询中Update方法的复杂度

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

使用平方根分解技术改进范围最小查询中Update方法的复杂度

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

java

algorithm

rmq