Count numbers less than $K$ in array

Question

Let's say we have given array $A$ consisting of $n$ integers, and integer $K$. Now we want to count number of indexes $i$ such that $A_i<K$. What is the easiest way to pre-process the array and answer queries for different $K$ fast. Note that the elements of the array will be small up to 10ドル^5,ドル so it will be possible to count how many times each elements appears.

For example, let $A = \{1, 2, 3,0,0,2\}, K =3$ the answer is 5ドル,ドル because all $\{1,2,0,0,2\}$ are less than 3ドル$.

I know that we can implement this with segment tree and than answer queries in $O(\log N),ドル but I was thinking that we can implement easier solution that is easier to code.

• quicksort: Can't you just sort the array? Am I understanding the problem wrong?
• Juho: What's the problem with doing what you suggest, i.e., just compute the counts for each possible $K$ as a preprocessing step? This is surely easy, and maybe more efficient than you expect.

Answer 1

Here is a $O(1)$ solution after $O(n)$ preprocessing step, assuming that all elements are less than some number $C$ (in your case 10ドル^5$) in pseudocode

count = new int[C] (array of integers)
for every a[i] in a 
 count[a[i]]++
for i = 1, i < C, i++ 
 count[i] += count[i-1] 

To Answer a query for a given k you just return count[k - 1]

• D.W.: That's not $O(n)$ preprocessing; it's $O(\max(n,C)),ドル which might be much slower if the array contains a large number (much larger than $n$).
• User Not Found: @D.W. Quoted from the question : "Note that the elements of the array will be small up to 10ドル^5$"

Answer 2

As mentioned in comments, you can sort the array as a pre-process. Then answer to the query in $O(\log(n))$ using binary search. The implementation is common and easier.