错误答案 - 无法找到 Bug - 使用线段树进行范围最小查询

Question

我正在尝试通过https://www.topcoder.com/community/data-science/data-science-tutorials/range-minimum-query-and-lowest-common-ancestor/学习线段树在了解线段树的基础知识之后，我尝试解决 this 问题。但是只有一个测试用例通过了，而在第二个测试用例中，我感到很沮丧。在使用 filediff 比较两个答案的进一步检查中，我发现有错误的答案。我找不到任何错误。请帮忙。

此代码用于创建和更新线段树。

变量 - 节点 = 线段树中的起始索引为 1。 b = 下限，e = 上限

static void preProcess(int node, int b, int e, int[] segTree, int[] arr) {

    if(b == e){ //base case
        segTree[node] = b;
        return;
    }

    preProcess(node << 1, b, (b+e)>>1, segTree, arr); 
    preProcess((node << 1) + 1, ((b+e)>>1) + 1, e, segTree, arr);
    if(arr[segTree[node<<1]] <= arr[segTree[(node << 1) + 1]]) {
        segTree[node] = segTree[node<<1];
        return;
    }
    segTree[node] = segTree[(node<<1) + 1];


}

现在，这段代码用于从树中查询最小索引。

    static int query(int node, int b, int e, int[] segTree, int[] arr, int i, int j) {
    // System.out.println(i+" "+j);
    // System.out.println(b+" "+e);
    if(i > e || j < b) {
        return -1;
    }
    if(b >= i && e <= j) {
        return segTree[node];
    }

    int p1 = query(node<<1, b, (b+e)>>1, segTree, arr, i, j);
    int p2 = query((node << 1) + 1, ((b+e)>>1) + 1, e, segTree, arr, i , j);
    if(p1 == -1) {
        segTree[node] = p2;
        return p2;
    }
    if( p2 == -1) {
        segTree[node] = p1;
        return p1;
    }
    if(arr[p1] <= arr[p2]) {
        segTree[node] = p1;
        return p1;
    }
    segTree[node] = p2;
    return p2;
}

这用于更新原始数组中的索引。

static void updateIndex(int index, int value, int[] arr) {
    arr[index - 1] = value;
}

我正在使用第一个索引中的段数组。有关完整代码，请参阅 here

现在我已经更改了一些代码，以防在从看到后发生更新，但现在我得到了错误的答案 -:

static void afterUpdate(int node, int b, int e,int index, int y,int[] segTree, int[] arr) {
     if(b == e){
         segTree[node] = index;
         return;
     }
     int mid = ((b+e)>>1);
     if(b <= index && mid >= index){
         afterUpdate((node<<1),b,mid,index,y,segTree,arr);
     }
     else {
         afterUpdate((node<<1)+1,mid+1,e,index,y,segTree,arr);
     }
     if(arr[segTree[node<<1]] <= arr[segTree[(node<<1)+1]]){
         segTree[node] = segTree[node<<1];
     }
     else 
        segTree[node] = segTree[(node << 1)+1];
 }

有关更新的完整代码，请参阅 here

Answer 1

您正在更新线段树以查询最小索引。删除它，代码工作正常。在查询的情况下，不应更改 segTree。

错误答案 - 无法找到 Bug - 使用线段树进行范围最小查询

Wrong Answer - Unable To Find Bug - Range Minimum Query Using Segment Trees

java

algorithm

segment-tree

rmq