次のような問題を考えました。
サイズ n の整数の配列 A があり、テスト ケース t があり、すべてのテスト ケースで数値 m と範囲 [s,e] が与えられます。つまり、s と e が与えられ、最も近いものを見つける必要があります。その配列の範囲内の m の数 (A[s]-A[e])。
インデックス付きの配列は 1 から n であると想定できます。
例えば：
A = {5, 12, 9, 18, 19}
m = 13
s = 4 and e = 5
したがって、答えは 18 になるはずです。
制約:
n<=10^5
t<=n
私が考えることができるのは、すべてのテスト ケースの O(n) ソリューションだけであり、より良いソリューションが存在すると思います。
これは大まかなスケッチです。データからセグメント ツリーを作成します。各ノードでは、左右のインデックスなどの通常のデータに加えて、そのノードをルートとするサブツリーにある数値も格納し、ソート順に格納します。ボトムアップの順序でセグメント ツリーを構築すると、これを実現できます。リーフのすぐ上のノードに、2 つのリーフ値をソート順に格納します。中間ノードでは、左側の子と右側の子に数値を保持し、標準の結合を使用して結合できます。ツリーには O(n) 個のノードがあり、このデータを維持するには全体で O(nlog(n)) かかります。
このツリーを取得したら、クエリごとに、指定された範囲 ([s, e]) 内の適切なノードに到達するまでパスをたどります。チュートリアルが示すように、1 つ以上の異なるノードが組み合わされて、指定された範囲が形成されます。ツリーの深さは O(log(n)) であるため、クエリごとにこれらのノードに到達するのにかかる時間です。各クエリは O(log(n)) である必要があります。完全に範囲内にあるすべてのノードについて、それらのノードに格納されている並べ替えられた配列で二分探索を使用して最も近い数値を見つけます。繰り返しますが、O(log(n)) です。これらすべての中で最も近いものを見つけてください。それが答えです。したがって、各クエリに O(log(n)) 時間で回答できます。
私がリンクしているチュートリアルには、スパース テーブルなど、実装が簡単な他のデータ構造が含まれており、クエリごとに O(sqrt(n)) を与える必要があります。しかし、私はこれについてあまり考えていません。
より速い解決策は存在しないと確信しています。あなたの問題のわずかなバリエーションは次のとおりです。
配列 A はありませんが、各テスト ケースには、検索する番号の並べ替えられていない配列が含まれています。(s から e までの A の配列スライス)。
その場合、各テスト ケースの線形検索よりも優れた方法は明らかにありません。
では、元の問題は上記のバリエーションより具体的にはどのような点でしょうか? 追加された唯一の情報は、すべてのスライスが同じ配列からのものであるということです。この追加の制約をアルゴリズムの高速化に使用できるとは思いません。
編集：私は訂正しました。セグメント ツリー データ構造が機能するはずです。
配列をソートし、二分探索を行います。複雑さ: o(nlogn + logn *t)