algorithm - 範囲最小クエリアプローチ (ツリーから制限付き RMQ へ)

Question

そこで、 RMQ (Range Minimum Query) に関するこのTopCoder チュートリアルを読んだところ、大きな疑問が生じました。

彼がアプローチを紹介したセクションで、私が今までに理解できることは次のとおりです。

(全体のアプローチは、実際にはスパース テーブル (ST) アルゴリズム、 LCA から RMQ への削減、およびRMQからLCA への削減で導入された方法論を使用します)

配列 A[N] が与えられた場合、それをデカルト ツリーに変換する必要があります。したがって、RMQ 問題を LCA (Lowest Common Ancestor) 問題にします。後で、配列 A の単純化されたバージョンを取得して、制限付き RMQ 問題にすることができます。

つまり、基本的には 2 つの変換です。したがって、RMQ から LCA への最初の部分は単純です。スタックを使用することで、O(n) 時間で変換を行うことができ、配列 T[N] が得られます。ここで、T[i] は要素 i の親です。そしてツリーが完成。

しかし、ここで私が理解できないことがあります。O(n) アプローチには配列 where が必要であり、その配列はチュートリアルのLCA から RMQ への削減|A[i] - A[i-1]| = 1セクションで紹介されています。これには、このツリーのオイラー ツアーが含まれます。しかし、変換の最終結果でこれをどのように達成できますか? それに対する私のアプローチは線形ではないため、このアプローチでは悪いと見なす必要があります。これに対する線形アプローチは何でしょうか?

更新：私を混乱させるポイント

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] には各要素のルートのみがあり、子はありません。