Exercise 8.2.4
Describe an algorithm that, given integers in the range to , preprocesses its input and then answers any query about how many of the integers fall into a range in time. Your algorithm should use preprocessing time.
This is not even challenging.
We just take the part of COUNTING-SORT
that builds up the array C
. Whenever
we want to count the number of integers in , we take C[b] - C[a-1]
(where C[-1] = 0
). This yields the number of integers in the given range.