6

RMQ 問題は次のように拡張できます。

n整数の配列が与えられますA。

query(x, y): 2 つの整数 1 ≤ x, y≤が与えられnた場合、 の最小値を見つけますA[x], A[x+1], ... A[y]。

update(x, v):与えられた整数vと 1 ≤ x≤ ndo A[x] = v.

この問題は、セグメント ツリーO(log n)を使用する両方の操作で解決できます。

これは紙の上では効率的な解決策ですが、実際には、特に再帰的に実装する場合、セグメント ツリーには多くのオーバーヘッドが伴います。

O(log^2 n)バイナリインデックスツリーを使用して、操作の1つ（または両方、よくわかりません）の問題を解決する方法があることを私は知っています（より多くのリソースが見つかりますが、これとこれはIMOです。それぞれ最も簡潔で網羅的です)。このソリューションは、 の値がnメモリに収まるため、BIT のオーバーヘッドがはるかに少ないため、実際には高速です。

ただし、特定の操作を実行するために BIT 構造がどのように使用されるかはわかりません。たとえば、間隔の合計を照会するためにそれを使用する方法しか知りません。最小値を見つけるためにどのように使用できますか?

それが役立つ場合、私が求めていることを実行する他の人が書いたコードがありますが、それを理解することはできません. そのようなコードの 1 つを次に示します。

int que( int l, int r ) {
    int p, q, m = 0;

    for( p=r-(r&-r); l<=r; r=p, p-=p&-p ) {
        q = ( p+1 >= l ) ? T[r] : (p=r-1) + 1;
        if( a[m] < a[q] )
            m = q;
    }

    return m;
}

void upd( int x ) {
    int y, z;
    for( y = x; x <= N; x += x & -x )
        if( T[x] == y ) {
            z = que( x-(x&-x) + 1, x-1 );
            T[x] = (a[z] > a[x]) ? z : x;
        }
        else
            if( a[ T[x] ] < a[ y ] )
                T[x] = y;
}

上記のコードでTは、 は 0 で初期化されa、指定された配列とNそのサイズ (何らかの理由で 1 からのインデックス付けを行います) でありupd、すべての読み取り値に対して最初に呼び出されます。upd呼び出される前にa[x] = v実行されます。

また、p & -pは一部の BIT ソースの と同じでありp ^ (p & (p - 1))、インデックスは 1 から始まり、ゼロ要素が無限大に初期化されます。

上記がどのように機能するか、またはBITで特定の問題を解決する方法を誰かが説明できますか?

4

3 に答える 3

3

コードを詳しく見ていませんが、次のスキームとほぼ一致しているようです。

1) BIT の構造を保持します。つまり、配列に 2 のべき乗に基づくツリー構造を課します。

2) ツリーの各ノードで、そのノードの子孫で見つかった最小値を保持します。

3) 任意の範囲を指定して、範囲の開始点と終了点にポインターを置き、それらが合うまで両方を上に移動します。ポインタを上に移動して他のポインタに近づけると、すべての子孫が範囲のメンバーであるノードに入ったので、そのノードの値に注意してください。ポインターを上に移動して他のポインターから離すと、結合したばかりのノードは、範囲外の値を含む値から導出された最小値を記録し、範囲内のそのノードの下にあるすべての関連値を既に記録しているため、無視します。そのノードの値。

4) 2 つのポインターが同じポインターになると、範囲内の最小値は、メモした任意のノードの最小値になります。

于 2013-06-18T04:28:59.450 に答える
2

少しいじるより上のレベルから、これは私たちが持っているものです:

g整数データ配列の通常の BIT 配列には、a範囲の合計が格納されます。

g[k] = sum{ i = D(k) + 1 .. k } a[i]

ここで、最下位の 1 ビットが 0 に設定されています。代わりD(k)にk

T[k] = min{ i = D(k) + 1 .. k } a[i]

このクエリは、通常の BIT 範囲合計クエリとまったく同じように機能しますが、クエリが進むにつれて、合計ではなく部分範囲の最小値が取得されるという変更があります。の N 項目のa場合、実行時間を決定するシーリング (log N) ビットが N にあります。

O(log N) サブレンジの最小値 (つまり、の要素)gが変更の影響を受け、それぞれが O(log N) クエリを単独で解決する必要があるため、更新にはより多くの作業が必要です。これにより、更新全体が O(log^2 n) になります。

少しいじるレベルでは、これは非常に巧妙なコードです。このステートメントx += x & -xは、最下位の連続する 1 の文字列をクリアしx、次に上位の 0 を 1 に設定します。これは、元の integer の BIT を「トラバース」するために必要なものですx。

于 2013-06-18T12:51:35.530 に答える
0

セグメント ツリーは、実際にも効率的なソリューションです。ただし、それらをツリーとして実装することはありません。次の 2 の累乗に切り上げ、 sizenの配列を使用します。の最後のエントリはです。なら、。範囲最小クエリに答えるには、の対数的に多くのエントリを調べるだけで済みます。また、 のエントリが更新されたときに、の対数的に多くのエントリを更新するだけで済みます。rmq2*nnrmqAj < nrmq[j] = min(rmq[2*j], rmq[2*j+1])rmqrmqA

私はあなたのコードを理解していないので、それについてコメントするつもりはありません。

于 2013-06-18T00:10:01.940 に答える