シーケンスの2つの項目の間の最小値

Question

以下にすばやく応答する（O（logn））ために、シーケンスをO（N）時間の配列に保存するプログラムを作成しようとしています。

min（int i、int j）：配置iとjの間のシーケンス内の最小値の位置を返します。

たとえば、シーケンスがA =（22,51,83,42,90,102,114,35）で、iがmin（3,6） を呼び出すと、42 < 83,90,102が返されます。

シーケンスの値がソートされていない場合や、バイナリツリーを実装しようと思ったO（logn）を取得したいので、すばやく時間を稼ぐことはできません。

問題は、私が必要とするようにmin（）のためにすぐにアクセスするために、バイナリツリーにシーケンスの値をどのように置くべきかを分かりません。

Answer 1

これは、区間ツリーで解決される典型的な問題です。 O(n)時にそれを構築し、O(log n)でクエリを実行することができます。

一般的な考え方は、インデックスiのノードがインデックス2iと2i+1の子を持つ配列に格納された完全なバイナリツリーを持つことです。葉にはシーケンスの値を格納し、非リーフノードにはすべての子孫の最小値を格納します。葉から樹木を上に構築する場合は、O(n)時にそれを行うことができます。 aとb

再帰的に下向きに行くの葉から根に向かう

• ：
  あなたは、2つの基本的なアプローチ（O(log n)時間の両方の仕事を）取ることができ、インターバル[a; b]のクエリを実行するにはツリールートから始める

「インターバルツリー」のフレーズでインターネット上で簡単に見つけることができる両方の方法の説明。あなたの問題のために、私はそれが少し速くなければならないので、前者を間違いなく推奨します。

要望通り、私はツリーを照会するための指示で答えを拡張しました。私があなたの問題について提案したボトムアップアプローチを詳しく見てみましょう。配列は0からn - 1に索引付けされていると仮定します。私はまたnがkのために2^kに等しいと仮定します。そうでない場合は、最小値を問い合わせる場合に、最下位レベルの末尾に+Inf要素を追加して、2の最も近い累乗に増加させます。これは有効なクエリには影響しません。また、前に説明したように簡単にインデックスを付けることができる完全なバイナリツリーを取得します。快適な実装のために、私は根のインデックス1を使用することをお勧めします、そして、これはまた、この記述のために仮定されます。

この図は物事をより明確にするはずです。下の黒のインデックスは元の配列のインデックスです。各ノードの隣の緑色のインデックスは、ツリー内のインデックスです。ここでは、クエリの例に関連する矩形を無視します。 query(a, b)ことで

我々は間隔[a; b]（包括的）で最小のクエリを意味しようとしています。まず、特殊ケース：aがbに等しい場合、tree[n + a]を返すだけです（tree[1]がルートの場合は、これは正しいインデックスです）。

a != bより複雑なケースに移りましょう。アルゴリズムの手掛かりは、任意の区間を共通の要素を持たず、元の区間を完全にカバーするO(log n)の基底区間に分割できることです。各ベース間隔の大きさは2の累乗であり、各ベース間隔は1つのノードで表されます。関連するすべての間隔をリストアップするときには、ノードの最小値を取ってquery(a, b)の答えを得るだけでよい。

ここでは、ベース間隔の選択方法について説明します。サンプル画像では、すべて四角で囲まれています。次のコードスニペットをご覧ください。

int x = a + n; 
int y = b + n; 
int result = Math.min(tree[x], tree[y]); 

while (x/2 != y/2) { 
    if (x % 2 == 0) { 
     result = Math.min(result, tree[x + 1]); 
    } 
    if (y % 2 == 1) { 
     result = Math.min(result, tree[y - 1]); 
    } 

    x /= 2; 
    y /= 2; 
} 

まず、元のインデックスをツリーのインデックスに変換します。次に、クエリの境界を含む単一項目の間隔を考慮します。 a == bの場合、私は特別なケースを除外したことに注意してください。

アルゴリズムは次のように進行し、ツリーを上に移動します。 x % 2 == 0の場合は、ツリー内の兄弟の間隔であるxを考慮します。この兄弟が常に[a; b]の間隔に完全に含まれていることを確認してください。 y % 2 == 1の場合と同じですが、兄弟はyの左側にあります。 x/2 == y/2の場合は、xとyが兄弟であることを意味し、アルゴリズムを停止する必要があります。このアプローチでは、[a; b]を完全にカバーする方法で間隔を選択することを自分で確認できます。

ツリーの最下位レベルにあるノードを最大で4つまで確認できます。お互いのレベルでは、2つ以上のノードをチェックしません。ツリーのレベルがO(log n)であるため、どのクエリの時間複雑度もO(log n)であることがわかります。

ボーナス - 配列を変更する。あなたが記述した問題は、配列の変更を必要としませんが、基本的なケースではとてもきれいなのでここでそれを追加します。また命令を処理したい場合は、array[a] = vを意味しますので、O(log n)の時間に簡単に実行できます。最初にtree[a + n] = vと設定し、パス上の最小値を更新するルートに行くよりも。