ある範囲内の整数を数えるためのデータ構造？

Question

質問：範囲内

与えられるn個の整数値[1、k]は、その入力を前処理し、次いで は、B≤、1≤aとbの間の値を持っているどのように多くのn個の整数の約任意のクエリに答えますk は2つのパラメータです。あなたのアルゴリズムはO（n + k）の前処理時間を使うべきです。

Answer 1

あなたのアルゴリズムはかなり良いですが、はるかに高速にすることができます。具体的には、アルゴリズムにはO（1）の前処理時間がありますが、分割ステップを実行するのに必要な時間の線形コストのため、クエリごとにO（n）時間を費やします。

別のアプローチを考えてみましょう。すべての値がソート順であるとします。この場合、下限のインデックスを見つけるための最初のバイナリ検索と上限を見つけるための2番目の検索の2つのバイナリ検索を行うだけで、範囲内の要素の数を非常に迅速に見つけることができます。インデックス。これは時間O（log n）を要する。入力配列を時間O（n + k）でソートするために入力配列を前処理することができれば、このアプローチは指数関数的に高速な検索時間をもたらすでしょう。

@minitechが指摘しているように、この並べ替えを行うには、1からkまでの整数に対して時間O（n + k）でソートするカウントソートアルゴリズムを使用できます。したがって、カウントソートとバイナリ検索の両方を併用すると、O（n + k）セットアップ時間とO（log n）クエリ時間が与えられます。

効率を上げるためにメモリを交換するつもりなら、これをさらに高速化できます。 kが適度に小さい数（例えば、100以下）であるとしましょう。あなたがO（k）空間を使っても大丈夫なら、O（1）時間にこれらの質問に答えることができます。その考え方は次のとおりです。各要素kについて、元の配列の要素数をkよりも小さく表すk要素の表を構築します。この配列を持っていれば、bより小さい要素の数とaより小さい要素の数（O（1）でそれぞれ）を調べ、それらを減算することで、ある範囲内の要素の総数を見つけることができます。

もちろん、これを行うには、このテーブルを時間O（n + k）に実際に構築する必要があります。これは次のようにして行うことができます。まず、k個の要素の配列を作成し、元のn要素の配列を反復し、各要素に対して、この番号に対応する表内の点をインクリメントします。 （時間O（n + k）で）完了したら、このテーブルに範囲1〜kの各値が元の配列に存在する回数を入力します（これは、ソートの計算方法）。次に、累積頻度を保持するk個の要素の第2の表を作成します。次に、最初のステップで作成したヒストグラムを繰り返し、累積頻度テーブルにヒストグラムを横切って遭遇した累積合計数を入力します。この最後のステップはセットアップのための総計時間O（n + k）の間、時間O（k）を要する。これで、時刻O（1）の質問に答えることができます。

希望すると便利です。

Answer 2

もう一つの簡単なアルゴリズムがあります。まず、サイズkの配列Aを割り当て、次にn個の要素を繰り返し、各整数x A [x]を1だけインクリメントします。これはO（n）時間かかるでしょう。 次に、配列Aのprefix sumを計算し、配列Bとして格納します。これはO（k）になります。ポイントのいずれかのクエリ（a、b）は、あなたが簡単に返すことができるようになりまし

：B [B] -B [A] + A [A]