0

このチュートリアルで、関数がノード インデックスを返すだけでなく、最後の 4 行のコードquery()の内容を変更するのはなぜですか?M

彼のアプローチには問題があると思います。変更された M 配列はm[node]、最近のクエリのインデックスを格納するため、将来の RMQ [range minimum Queries] を処理できなくなります。

これが私が話しているコードです:

int query(int node, int b, int e, int M[MAXIND], int A[MAXN], int i, int j)
{
    int p1, p2;

    // if the current interval doesn't intersect 
    // the query interval return -1
    if (i > e || j < b)
        return -1;

    // if the current interval is included in 
    // the query interval return M[node]
    if (b >= i && e <= j)
        return M[node];

    // compute the minimum position in the 
    // left and right part of the interval
    p1 = query(2 * node, b, (b + e) / 2, M, A, i, j);
    p2 = query(2 * node + 1, (b + e) / 2 + 1, e, M, A, i, j);

    // return the position where the overall 
    // minimum is
    if (p1 == -1)
        return M[node] = p2;
    if (p2 == -1)
        return M[node] = p1;
    if (A[p1] <= A[p2])
        return M[node] = p1;
    return M[node] = p2;
}
4

1 に答える 1

1

それは間違いなくバグです。そうです、配列を更新せずにインデックスを返すだけです。

于 2014-11-06T15:45:43.387 に答える