Answer:
Explanation:
Assume that our integers are stored in array A[1 · · · n] and thus, length[A] = n. We need two additional arrays B[1 · · · k] and C[1 · · · k].
Our algorithm will first initialize all elements of array B to 0. This step
requires O(k) time.
Next, for each element of array A (i.e., A[i] for i = 1, 2, · · · , n), we will increment
B[A[i]]. Observe that this step will require O(n) time and B[j] for j = 1, 2, · · · , k, now contains the number
of elements of A having value j. Finally, make C[1] = B[1] and for each element l of array C where
l = 2, 3, · · · , k, we will compute C[l] = B[l] + B[l − 1]. This step takes O(k) time.
Now, to answer any query about how many of n integers fall into a range [a · · · b], we simply compute
C[b] − C[a] + B[a].
Observe that this computation requires only O(1) time after the O(n + k) preprocessing
time.
