範囲最小クエリ<O(n), O(1)>（ツリーから制限付きRMQへ）

Question

したがって、私はthis RMQ（Range Minimum Query）に関するTopCoderチュートリアルを読んで、大きな質問を受けました。彼は私が今まで理解できるか、 approachを導入セクションで

はこれです：

（全体的なアプローチは、実際に、Sparse Table (ST) Algorithmで導入された方法論を使用していますReduction from LCA to RMQ、およびfrom RMQ to LCA）

配列Aを考えます[N]、それをデカルトツリーに変換し、RMQ問題をLCA（Lowest Common Ancestor）問題にする必要があります。後で、配列Aの簡略化されたバージョンを取得し、それを制限されたRMQ問題にすることができます。

これは基本的に2つの変換です。最初のRMQからLCAまでの部分はシンプルです。スタックを使用することによって、O（n）回の変換を行うことができ、配列T [N]となり、T [i]は要素iの親である。そして木は完成した。

ここで私は理解できないことがあります。 O（n）のアプローチでは、配列が|A[i] - A[i-1]| = 1であり、その配列はチュートリアルのReduction from LCA to RMQセクションに導入されています。それはこの木のオイラーツアーを含む。しかし、私の最終的な結果からどのようにこれを達成できますか？私のアプローチは線形ではないので、このアプローチでは悪いと考えるべきですが、これには線形アプローチがありますか？

UPDATE：木の絵私

Here's the array A[]: 

    n : 0 1 2 3 4 5 6 7 8 9 
A[n]: 2 4 3 1 6 7 8 9 1 7 

Here's the array T[]: 

    n : 0 1 2 3 4 5 6 7 8 9 
T[n]: 3 2 0 * 8 4 5 6 3 8 // * denotes -1, which is the root of the tree 

//Above is from RMQ to LCA, it's from LCA to RMQ part that confuses me, more below. 

を混同ポイント：

オイラーツアーがちょうどDFS（深さ優先のように、各ノードの子を知っている必要があります最初の検索）、T [n]は各要素のルートのみを持ち、子はありません。ここで

Answer 1

はあなたを混乱何の私の現在の理解である：LCAにRMQを低減させるために

1. 、あなたは木に配列を変換し、そのツリーのオイラーツアーを行う必要があります。
2. オイラーツアーを行うには、各ノードがその子を指すようにツリーを保存する必要があります。
3. RMQからLCAにリストされている削減は、各ノードがその親を指しており、その子は指していません。

これが当てはまる場合、あなたの懸念事項は完全に正当なものですが、これを簡単に解決する方法があります。具体的には、すべての親ポインタの配列を取得したら、各ノードがO（n）時間にその子を指すツリーに変換することができます。考え方は次のとおりです。

• n個のノードの配列を作成します。各ノードは、値フィールド、左の子、および右の子を有する。
• 最初に、n番目のノードがnullの左の子、nullの正しい子、および配列のn番目の要素の値を持つように設定します。
• （T [n]はn個の親指標である）T配列を横切って反復とは、次の操作を行います。
  • Tは、[N] = *、次にn番目のエントリがルートである場合。後で使用するために保存することができます。
  • そうでなければ、T [n] < nなら、ノードnは親の右の子でなければならず、位置T [n]に格納されていなければなりません。したがって、T [n]番目のノードの右の子をn番目のノードに設定します。
  • そうでなければ、T [n]> nなら、ノードnは、親の左の子でなければならず、位置T [n]に格納されている必要があります。したがって、T [n]番目のノードの左の子をn番目のノードに設定します。

各ノードを正確に一度だけ処理されるので、これは、時間O（N）で実行されます。

これが完了したら、必要なツリー構造を明示的に構築し、ルートへのポインタを持っています。そこから、アルゴリズムの残りの部分を進めるのは合理的に簡単です。

希望すると便利です。