(20 points) Let A[1], A[2], . . ., A[n], be n integers (possibly with repetitions) in the range 1 . . . k i.e. all the entries of the array A are between 1 and k. You want to repeatedly answer range queries of the form [a, b] where 1 a b k; each range query asks how many A[i]s are in the range a . . . b, i.e., how many numbers from A lie between a and b. For example, if k = 10, and the array A has seven elements 5, 9, 3, 5, 10, 6, 1, 7 the range query [2, 7] asks how many numbers are there in the array A between 2 and 7, so the answer should be 5 (because the numbers 3,5,5,6,7 from A lie in the range [2, 7]). You want to do this efficiently. In order to do this, you first do some preprocessing, which is a one-time operation i.e. you are willing to pay the one-time relatively expensive cost of doing preprocessing before starting to answer the range queries, in order to save time with the many range queries which will follow. Your algorithm should work within the following time bounds:

Hint:

Think about counting sort discussed in class and in the textbook. You will need to keep the auxillary array C[1..k] we used for counting sort where C[j] represents the number of elements from A which are less than or equal to j. In the above example, C[2] will be 1 since there is one element (i.e. 1) in A which is 2; C[7] will be 6 since there are 6 elements (i.e. 1,3,5,5,6,7) which are 7. In class we saw how to fill C in time O(n + k) (this is the preprocessing step), and once the array C is available, you should show how to use it to answer range queries in O(1) time.