java - 不正解 - バグが見つからない - セグメント ツリーを使用した範囲最小クエリ

Question

https://www.topcoder.com/community/data-science/data-science-tutorials/range-minimum-query-and-lowest-common-ancestor/ セグメントの基本を理解した後、セグメントツリーを学習しようとしていますこの質問を解決しようとしました。しかし、合格したテスト ケースは 1 つだけで、2 つ目のテスト ケースでは問題が発生しています。filediff を使用して 2 つの回答を比較してさらに調べたところ、間違った回答があることがわかりました。エラーが見つかりません。助けてください。

このコードは、セグメント ツリーを作成および更新するためのものです。

変数 - node = 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];
 }

更新された完全なコードについては、こちらを参照してください