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:

The one time preprocessing step should take O(n + k) time.

Each range query should be answered in O(1) (i.e. constant) time i.e. the amount of time to answer the range query [a, b] will be a small number which will in no way depend on n,k,A,a,b or the number of elements which actually lie in the range [a, b].

(a) Give a clear description of your algorithm for the above problem. This description should include both how the preprocessing step is carried out, and then how the range queries are answered.

(b) Trace your algorithm on the above example i.e. for the array A as above, show what will happen in the preprocessing step. Then show how the algorithm will answer the range query [2, 7]. Also show how the algorithm will answer the range query [1, 9].

(c) Do a worst case time analysis (use big O notation) of your algorithm i.e. answer the two questions: how much time does the preprocessing step take and how much time does answering the range query take.