Regarding this question:
You are given an unsorted array $A$ of $n$ integers in the range $2^n −10n \leq A[i] \leq 2^n$. Suggest a data structure that allows to answer in $O(1)$ steps the number of keys in the range $a$ to $b$ (note that $a, b$ are not necessarily integers). The construction of data structure should cost at most $O(n)$ steps.
- Describe in few sentences the data structure.
- Write a pseudocode for constructing the data structure.
- Write a pseudocode for the
- Give a short explanation of the time and space complexity of (2) and (3).
Can someone please explain me what "the number of keys in the range $a$ to $b$" means?