Question

Describe an algorithm that, given n integers in range 0 to k, preprocesses its input and then answers any query about how many of the n integers fall into a range [a...b] in O(1) time. Your algorithm should use O(n+k) preprocessing time.

Answer 1

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.