問題タブ [cartesian-tree]

そこで、 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セクションで紹介されています。これには、このツリーのオイラー ツアーが含まれます。しかし、変換の最終結果でこれをどのように達成できますか? それに対する私のアプローチは線形ではないため、このアプローチでは悪いと見なす必要があります。これに対する線形アプローチは何でしょうか?

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

ツリーの写真:

オイラー ツアーでは、DFS (深さ優先検索) と同様に、各ノードの子を知る必要がありますが、T[n] には各要素のルートのみがあり、子はありません。

O(n)時間で配列をデカルトツリーに変換する方法を知っています

1. http://en.wikipedia.org/wiki/Cartesian_tree#Efficient_constructionおよび
2. http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor#RMQから LCA へ

ただし、少なくともデカルト ツリーのすべてのノードに左右のポインターを関連付ける必要があるため、必要なメモリ量が多すぎます (定数)。

これらの定数を（うまくいけば1に）減らすために行われた作業に私をリンクできますか？

データ構造コースでテストを受けましたが、質問の 1 つは次のとおりでした。

o(1) の複雑さで配列内の 2 つの数値の間の最小値を与える範囲最小クエリで維持される n サイズの配列があるとします。もちろん、配列はさまざまなオプションの動的計画法を使用して RMQ に応答するように準備された o(n) でした。問題は、配列内の 1 つのオブジェクト (数値) を変更した場合、o(1) で RMQ を見つけることができるようにするために行った準備をどのように変更すればよいか、そしてそれにはどのような複雑さが必要かということです。

答えは、o(n) で新しい RMQ を作成することではありません。それより小さくする必要があります。

この問題は宿題ではありません。理解するためにテストをやりたいだけです。

前もって感謝します。

与えられた配列 A があるとします。今、フォームの複数の操作があります。

と

配列 Ai..j を出力します。

例 、

デカルト木でできると聞いたことがあります。ここでブログを読んでいます が、デカルトツリーを使用してこれを行う方法をまだ理解できません。キーと値は何であり、どのように実装する必要がありますか?

The input is an array (n*m 1<n,m< 1000). I have to find the maximum element in every sub-matrice of size( a*b ).

I was trying to do this by iterating x over n-a+1 and y over m-j+1.

• 2D segment trees or quad trees are not sufficiently fast as the number of queries is large.

• I tried to extend sparse table but was not able to due to shortage of space.

• I have read about solutions with Cartesian trees but some code is needed as I cannot understand it.

Please explain a solution that will answer a query in O(nm) time or in O(1) time by pre-computation. Also, the input array is static.

Note: although I've tried sparse table, it might not have been correct, so feel free to post a solution with it.

I'm a Java coder, so an implementation in Java or c/c++ would be great.

Also this is not a duplicate as I have searched a lot about it without finding anything suitable.