8.2-4 Describe an algorithm that, given n integers in the 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 $\theta(n + k)$ preprocessing time.
We can calculate array C as in counting sort it would take $\theta(n+k)$ to find the no of elements
If a-1 = 0
return c[b]
else
c[b] - c[a-1]
we cannot subtract c[b] and c[a] because we will loose occurrence of c[a](if their is one)
No comments:
Post a Comment