错误答案-无法找到错误-使用细分树的范围最小查询 [英] Wrong Answer - Unable To Find Bug - Range Minimum Query Using Segment Trees

问题描述

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

I am trying to learn segment tree through https://www.topcoder.com/community/data-science/data-science-tutorials/range-minimum-query-and-lowest-common-ancestor/ After Understanding the basics of segment trees I tried to solve this question. But only one test case is passed and on the second one, I am getting tle. On further inspection comparing the two answers using filediff I found out there are wrong answers. I am unable to find any errors. Please help.

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

this code is for creating and updating segment tree.

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

Variables - node = starting index in segment tree which is 1. b = lower limit, e = upper limit

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;
}

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

and this for updating an index in the original array.

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

我正在使用第一个索引中的细分数组。
有关完整代码，请参见此处

I am using the segment array from 1st index. For full code refer here

现在，如果从这里，但是现在我得到了错误的ans-：

Now I have changed bit of my code in case of if update happens after seeing from here but now I am getting Wrong ans -:

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];
 }

有关更新的完整代码，请参考此处

For updated full code refer here

推荐答案

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

You are updating the segment tree in case of querying the minimum index. Remove it and the code is working fine. In case of query the segTree should not be changed.

这篇关于错误答案-无法找到错误-使用细分树的范围最小查询的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！