0

我正在尝试通过https://www.topcoder.com/community/data-science/data-science-tutorials/range-minimum-query-and-lowest-common-ancestor/ 了解段的基础知识后学习段树树 我试图解决这个问题。但是只有一个测试用例通过了，而在第二个测试用例上，我开始感到厌烦了。在进一步检查使用 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;
}

我正在使用来自第一个索引的段数组。完整代码参考这里

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

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

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

4

1 回答 1

2

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

于 2017-09-10T17:21:50.850 回答