問題タブ [rmq]

A1、A2、...、AN として定義された N 個の整数 Ai があります。フォーム a の Q クエリを処理する必要があります。このようなクエリごとに、Ai ≥ a となるインデックス i を見つけます。そして、Ai-a の差を最小限に抑える必要があります。私はそれのようにやった

しかし、それは TLE につながります。それを行うための効率的な方法は何ですか？

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.

プロジェクトに追加しようとしRMQClient frameworkていXCODE 7.3ます。https://github.com/rabbitmq/rabbitmq-objc-clientおよびRabbitMQ公式サイトで指定されている手順に従っています。

フレームワークを追加して実行した後、Tools->Build私は受け取っています

エラー メッセージが表示され、フレームワークからヘッダー ファイルをインポートできません。この問題に対する提案はありますか？

サイズ1の A(0 indexed) という配列があります。

インデックス k1 (k1>=0) と A.size()-1 (つまり、最後の要素) の間の配列 A で最小値を見つけたいと考えています。

次に、配列の最後に値: (指定された範囲の最小要素 + いくつかの「ランダムな」定数) を挿入します。次に、インデックス k2 と A.size()-1 の間の最小値を見つけるための別のクエリがあります。最後に値 : (指定された範囲内の最小値 + 別の「ランダムな」定数) を挿入します。私はそのような多くのクエリを実行する必要があります。

たとえば、N 個のクエリがあるとします。単純なアプローチでは O(N^2) かかります。

配列が静的ではないため、セグメント ツリーを使用できません。しかし、賢明な方法は、サイズ N+1 配列のセグメント ツリーを作成することです。未知の値を無限大で埋めます。これにより、O(Nlog N) の複雑さが得られます。

NlogN の複雑さ、または N の他の方法はありますか?

セグメント ツリーの遅延伝播の問題に直面しています。私は配列A、長さ N 、より小さい配列 (最大長 20) を持っています。また、配列Aiで現在指しているインデックス i を参照する、インデックスBの配列もあります。

2 つの操作があります。a) 指定された範囲のBのポインターを更新して、次の要素を指すようにします。b) 指定された範囲内でポインターが現在指している値の最大値を出力します。

例えば：-

範囲 1,2 のクエリを作成すると、最大は 8 になります。これは、配列 B のポインターが配列の最初の要素を指しているためです。したがって、1,8 を使用しています。

2,3 max =8; のクエリを作成する場合。これは、値 8,3 を使用しているためです。一般に、

これらは、非常に単純な形式の 2 つの方法です。ただし、入力の制約が大きいため、O(logn) クエリと更新時間が必要です。そのため、セグメント ツリーを使用することを考えました (現在、複雑さは O(n^2) です)。遅延伝播で中間ノードを更新します。

どんな洞察も役に立ちます。また、同様の問題をオンラインでリンクできる場合は、私ができなかったので本当に役に立ちます（これはどのWebサイトからのものでもないため、そのようなものは知りません）。助けてくれてありがとう。

注: その場合は 1b[i]>a[i].lengthに置き換えa[i][b[i]]ます。

Range minimum queriesを見ています。

ウィキペディアは次のように述べています。

長さ n の配列に対して Θ(n²) 通りのクエリが可能です。

私はそれを理解していません。サイズ 5 の配列の例を次に示し
ます。次のクエリが可能です。

1 つのクエリ [0,4]
2 つのクエリ [0,3] および [1,4]
3 つのクエリ [0,2]、[1,3] および [2,4]
4 つのクエリ [0,1]、[1、 2]、[2,3]、[3,4]
5 つのクエリ [0]、[1]、[2]、[3]、[4]

可能なクエリの合計

[0,4] +
[0,3] + [1,4] +
[0,2] + [1,3] + [2,4] +
[0,1] +[1,2] + [2 ,3] + [3,4] +
[0] + [1] + [2] + [3] + [4]

----------------------------------
15クエリ

しかし、私はN^2 = 25クエリを期待しています ( N は配列サイズ = 5 です)

何が欠けていますか？誰でも説明できますか？