検索最も近い数が

Question

は私がある問題を考えましたと範囲[s、e]、つまりsとeが与えられ、その配列の範囲内で最も近いmの数を見つけなければなりません（A [s] -A [e]）。

インデックスの配列は1からnまでとすることができます。例えば

：私ができる

n<=10^5 
t<=n 

すべての思考は、すべてのテストケースのためのO（n）の溶液である：

A = {5, 12, 9, 18, 19} 
    m = 13 
    s = 4 and e = 5 

だから答えは18

制約でなければなりません私はよりよい解決策が存在すると思います。

Answer 1

これは概略のスケッチです： データからsegment treeを作成します。各ノードでは、左右のインデックスなどの通常のデータのほかに、ソート順に格納された、そのノードをルートとするサブツリーにある番号も格納します。これは、セグメントツリーをボトムアップ順に構築するときに実現できます。リーフのすぐ上のノードでは、2つのリーフ値をソート順に格納します。中間ノードでは、標準のマージを使用して結合できる左の子と右の子に数値を保持します。ツリーにはO（n）個のノードがあり、このデータを保持することは全体的なO（nlog（n））を取るべきです。

このツリーがあると、すべてのクエリに対して、指定された範囲（[s、e]）内の適切なノードに到達するまでパスを歩きます。チュートリアルが示すように、1つまたは複数の異なるノードが結合して指定された範囲を形成します。木の深さがO（log（n））であるので、これはこれらのノードに到達するクエリあたりの時間です。各クエリはO（log（n））でなければなりません。範囲内に完全にあるすべてのノードについて、それらのノードに格納されているソートされた配列内でバイナリ検索を使用して最も近い番号を見つけます。再び、O（log（n））。これらの中で最も近いものを見つけ、それが答えです。したがって、O（log（n））時間内に各クエリに答えることができます。

私がリンクするチュートリアルには、実装が簡単なスパーステーブルなどの他のデータ構造が含まれており、クエリごとにO（sqrt（n））を与える必要があります。しかし、私はこれについてはあまり考えなかった。

Answer 2

私はかなり速い解決策が存在しないと確信しています。

配列Aはありませんが、各テストケースには並べ替えられない番号の配列が含まれています。 （Aからsまでの配列スライス）。

この場合、各テストケースの線形検索よりも明らかに優れた方法はありません。

元の問題はどのように上記のバリエーションよりも具体的ですか？追加された唯一の情報は、すべてのスライスが同じ配列から来ていることです。私は、この追加の制約がアルゴリズムの高速化に使用できるとは思わない。

EDIT：私は訂正しました。セグメントツリーのデータ構造は機能するはずです。

Answer 3

アレイをソートしてバイナリ検索します。複雑さ：o（nlogn + logn * t）