-1

私はセグメント ツリーを学習しています(範囲最小クエリの例で) が、セグメント ツリーをクエリするためのアルゴリズムの一部の背後にある理由を理解するのに問題があります。

セグメントツリーの構築の部分を理解するのに問題はありませんが、この関数の理由を理解できません:

int RMQUtil(int *st, int ss, int se, int qs, int qe, int index)
{
    // If segment of this node is a part of given range, then return the min of the segment
    if (qs <= ss && qe >= se)
        return st[index];    // this is the part I am struggling with

    // If segment of this node is outside the given range
    if (se < qs || ss > qe)
        return INT_MAX;

    // If a part of this segment overlaps with the given range
    int mid = getMid(ss, se);
    return minVal(RMQUtil(st, ss, mid, qs, qe, 2*index+1), RMQUtil(st, mid+1, se, qs, qe, 2*index+2));
}

このノードのセグメントが指定された範囲の一部である場合、セグメントの最小値を返します。

4

2 に答える 2

0

このノードのセグメントが特定の範囲の一部である場合、サブセグメント [ss, se] (それは st[index] です) の答えは既にわかっているので、深く掘り下げる必要はありません。

于 2015-01-18T06:51:23.003 に答える
0

クエリでは、[qs,qe] の範囲で最小数を見つけたいとします。

ここで、これをセグメント ツリーで表すと、最初に間隔の中央を見つける、つまり mid=(qs+qe)/2 として表すことができます。

そして論理は、範囲 [qs,qe] の最小値は、範囲 [qs,mid] と [mid+1,qe] の最小値を見つける最小値に等しいということです。

これは、次の行の ur コードで記述されています。

int mid = getMid(ss, se);
    return minVal(RMQUtil(st, ss, mid, qs, qe, 2*index+1), RMQUtil(st, mid+1, se, qs, qe, 2*index+2));

于 2015-05-13T09:30:53.970 に答える