algorithm - 範囲内の整数の数を見つける

Question

私はアルゴリズムの第 3 版の紹介を読んでいて、次のことに遭遇しました。整数 a および b。それはブルートソリューションを持っていますが、入力の前処理フェーズによって、このクエリは Θ(1) 時間で完了することができ、この前処理フェーズには O(n+k) 時間がかかると言います。整数のソートを考えていますが、ソートには少なくとも O(n+k) を超える O(nlogn) 時間がかかります。前処理段階で何ができますか? ありがとう

Answer 1

数値は [0,k] の範囲にあるため、カウントソートを使用して O(n+k) 時間でソートできます。

カウントを取得したら、そのカウント配列のプレフィックス合計を取得できます。これにより、範囲 [0, a] 内の数値の数がわかります。O(k) 時間。

それを使用すると、O(1) 時間で、適切な差を取ることで [a,b] のクエリに答えることができます。