# Question: Describe an algorithm that given n integers in the range

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 Θ (n + k) preprocessing time.

**View Solution:**## Answer to relevant Questions

You are given a sequence of n elements to sort. The input sequence consists of n/k subsequences, each containing k elements. The elements in a given subsequence are all smaller than the elements in the succeeding subsequence ...Show that the second smallest of n elements can be found with n + ⌈lg n⌉ - 2 comparisons in the worst case.Suppose we use a hash function h to hash n distinct keys into an array T of length m, assuming simple uniform hashing, what is the expected number of collisions? More precisely, what is the expected cardinality of {{k, l} : ...Let us define a relaxed red-black tree as a binary search tree that satisfies red- black properties 1, 3, 4, and 5. In other words, the root may be either red or black. Consider a relaxed red-black tree T whose root is red. ...Observe that whenever the size field of a node is referenced in either OS-SELECT or OSRANK, it is used only to compute the rank of the node in the sub tree rooted at that node. Accordingly, suppose we store in each node its ...Post your question