Suggestion of a Data Structure

Question

Regarding this question:

You are given an unsorted array A of n integers in the range 2^n −10n ≤ A[i] ≤ 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.

1. Describe in few sentences the data structure.
2. Write a pseudocode for constructing the data structure.
3. Write a pseudocode for the numberKeys(NewDataStructure,a,b).
4. 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?

Appreciate your help!

Thanks!

Answer 1

"the number of keys in the range a to b" means DS must be able to answer range based query at any point time for any range. Like if there are 10 entries then find entry with value greater than 5 but less than 7.

Describe in few sentences the data structure.

Binary search tree based structure will work with each not having link to child node and a extra variable tracking range of child nodes.

Refer Binary search tree

Time to find the range node O(n). Time to find number of node in range is O(1) as we are going to calculate while building/creating the tree.

Answer 2

Let's say n=1000

Then you have an array of 1000 entries (=keys, integer values, numbers, ...) within the interval [2^1000-10000;2^1000].

A question could be:
How many array entries are in interval [2^1000-9321.7;2^1000-123.2]?