問題タブ [rmq]

アルゴリズムクラスの次の宿題の質問に困惑しています。

_{n 個の値 x 1}、 x _{2 ...} x _nのシーケンスが与えられ、次の形式の繰り返しクエリに_すばやく答えようとしているとします。

O(n) 空間を使用し、O(log n) 時間でクエリに応答するデータ構造を設計します。

まず、シーケンスがソートされたセットを参照するのか、ソートされていないセットを参照するのかはわかりません。

したがって、O(log N) ルックアップ時間について話している場合、これには明らかに二分木が必要であることがわかります。基本的に、 set がSあり、各要素をS二分木に挿入すると思います。問題は、質問は基本的に、ソートされていないセットへのインデックスの範囲が与えられたクエリに答える方法を考え出し、その範囲の最小値を O(log N) 時間で決定することです。そんなことがあるものか？セットの各数値がツリーに挿入されたとしても、私ができる最善の方法は、O(log N) 時間で特定の数値を検索することです。これにより、ソートされていない数値範囲の最小値を見つけることができませんS。

助言がありますか？

入力として array を受け取り、各、、前処理中、および各クエリaの範囲の最小値を見つけるClojure プロジェクトに取り組んでいます。(前処理には が必要ですが、同時実行 ( ) を使用し、配列を配列に分割することで、 でこの問題を解決できます)[i,j]ijO(n)O(1)O(n*log(n))pmapn/log nO(n)

そのため、配列をベクトルとして、行列をベクトルのベクトルとして表すことにしました。

これは C# の関数の 1 つです。

そして、これは私がClojureで書いた方法です：

まず、実行しようとすると、次のエラーが表示されます。

その上、私が書いたコードは、並列に動作するr場合、(行番号を表す)の値を変更する方法がわからないため、私が望んでいることを実行しません。apply_fnつまり、C#で変更するのが好きです:

( C#の-loop のrようなものです)ifor

前もって感謝します。

Range Minimum Queries のウィキペディアのリンクを読み、さらにいくつかのチュートリアル (topcoder およびその他のリンク) を見ましたが、非常に基本的な質問があります。

RMQ の正式な定義は次のとおりです: 順序付けられたセット (数値など) から取得されたオブジェクトの配列が与えられた場合、範囲最小クエリ (または RMQ) はサブ配列内の最小要素の位置を要求します。

私が理解できないのは、線形探索で問題を解決できないのはなぜですか? 配列 A[0...n] で、RMQ(i,j) が必要な場合

ループの終わりまでに、最小値と最小値が存在するインデックスがわかります。

私は間違いなくここに何かが欠けています...なぜRMQが必要なのか誰かが理解するのを手伝ってくれますか?

範囲最小クエリ問題を解決するために作成されたセグメント ツリーにノードがいくつあるかを知りたいです。

また、ビルド操作にかかる時間とその理由は?

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

前回の質問「範囲最小クエリアプローチ（ツリーから制限付きRMQまで） 」からの続き（読むことをお勧めします）

繰り返しになりますが、TopCoderに関するこのチュートリアルから、あちこちでいくつか質問があります。誰かがそれらを解決してくれることを願っています。

したがって、RMQ（範囲最小クエリ）問題をLCA（最小共通祖先）問題に変換してから、元に戻すと、単純化された配列を作成できます。（両方の変換はチュートリアルにあり、簡略化された配列は「LCAからRMQへ」で説明されている配列Lです）

とにかく、私はオイラーツアーを使用してその配列を取得できます。これがすべての計算の中心的な部分です。

まず、配列全体を1と-1だけで構成することで、さらに単純にする必要があります。これが私が行うことですLs[i] = L[i] - L[i-1]。

2番目のステップは実際にはパーティション化であり、それは十分に単純ですが、私を混乱させるこの3番目のステップがあります。

A'[i]をAのi番目のブロックの最小値とし、B[i]をAのこの最小値の位置とします。

Aはこの文のL配列を参照しているため、最小値は常に1または-1になり、複数の1と-1が存在することになります。これで計算が簡単になるとは思わないので、混乱します。

4番目のステップ、

ここで、セクション1で説明したSTアルゴリズムを使用してA'を前処理します。これには、O（N / l * log（N / l））= O（N）の時間とスペースが必要です。

A'が1と-1の記録しか保持しない場合、それに対して何もすることは役に立たないように思われます。

最後のステップ、

テーブルPにインデックスを付けるには、Aの各ブロックのタイプを前処理し、配列T [1、N/l]に格納します。ブロックタイプは、-1を0に、+1を1に置き換えて得られる2進数です。

どういう意味ですか？それぞれの組み合わせを計算するには？のように、000--..... 001？

複数の質問のように見えますが、誰かがこれらの最後のステップを案内してくれることを望んでいました。ありがとう！

前回の 2 つの質問「Range Minimum Query アプローチ (ツリーから制限付き RMQ へ)」と「Range Minimum Query アプローチ (最終ステップ)」の続きです。

私はTopCoder でこのチュートリアルに従いました。アプローチは最後のセクションで紹介されています。

すべてが完了したと仮定すると、クエリの準備が整いました。チュートリアルによると、これは私がすべきことです：

i と j は同じブロックにあるため、P と T で計算された値を使用します。

たとえば、次のようなブロックがあるとします。

最小値はもちろん 3 番目の 0 にありますが、i と j が 4 と 6 のようであれば、3 番目の 0 は照会された基準にはありません。私の理解は間違っていますか？

i と j は異なるブロックにあるため、3 つの値を計算します。P と T を使用して i から i のブロックの終わりまでの最小値、A' で事前に計算されたクエリを使用して i と j のブロックの間のすべてのブロックの最小値、およびj のブロックの先頭から j まで、ここでも T と P を使用します。最後に、計算したばかりの 3 つの値を使用して全体の最小値になる位置を返します。

i から i のブロックの終わりまでの最小値と、j のブロックの開始から j までの最小値を計算するのはなぜですか? どちらも答えは i...j の外にあるのではないですか？また、最後の質問のように完全に適合しない場合の方法。

こんにちは、RMQ 用に 2D レンジ ツリーを実装しようとしています。これが私のコードです。十分に効率的ではないと思います。最適化のためにできることはありますか。

ls には、すべてのノードでソートされた y のリストが含まれます

rt にはセグメント ツリーが含まれます

p.fi.fi には x 座標が含まれます

p.fi.se には y 座標が含まれます

p.seにはポイントのIDが含まれています

loc には、各 ID の x ノードと y ノードが含まれます

範囲ツリーの最初の実装なので、コードがめちゃくちゃだったらごめんなさい

私の現在の実装は約4秒間実行されますが、3秒未満で実行する必要があります。これが私の完全な 実装です

ありがとう ：）

私は10個の数字supprse A [10] = {1,2,3,4,5,6,7,8,9,10}への配列を持っており、特定の範囲で数字の乗算を計算する必要がありますが、得られません正解、私はセグメントツリーを使用していますが、クエリ操作の使用方法がわかりません これが私のコードです: