Data structure to check if a static array does not contain an element of a given range

Question

I'm stuck for hours on the following homework question for data-structures class:

You are given a static set S (i.e., S never changes) of n integers from {1, . . . , u}.

Describe a data structure of size O(n log u) that can answer the following queries in O(1) time:

Empty(i, j) - returns TRUE if and only if there is no element in S that is between i and j (where i and j are integers in {1, . . . , u}).

At first I thought of using a y-fast-trie.

Using y-fast-trie we can achieve O(n) space and O(loglogu) query (by finding the successor of i and check if it's bigger than j).

But O(loglogu) is not O(1)...

Then I thought maybe we can sort the array and create a second array of size n+1 of the ranges that are not in the array and then in the query we would check if [i, j] is a sub-range of one of the ranges but I didn't thought of any way to do it that uses O(nlogu) space and can answer the query in O(1).

I have no idea how to solve this and I feel like I'm not even close to the solution, any help would be nice.

Answer 1

We can create a x-fast-trie of S (takes O(nlogu) space) and save in each node the maximum and minimum value of a leaf in it's sub tree. Now we can use that to answer the Empty query in O(1). Like this:

Empty(i, j) We first calculate xor(i,j) now the number of leading zeros in that number will be the number of leading bits i and j share in common let's mark this number as k. Now we'll take the first k bits of i (or j because they're equal) and check in the x-fast-trie hash table if there's a node that equels to those bits. If there isn't we'll return TRUE because any number between i and j would also have the same k leading bits and since there isn't any number with those leading bits there isn't any number between i and j. If there is let's mark that node as X.

if X->right->minimum > j and X->left->maximum < i we return TRUE and otherwise we return FALSE, because if this is false then there is a number between i and j and if it's true then all the numbers that are smaller than j are also smaller than i and all the numbers that are bigger than i are also bigger than j.

Sorry for bad English

Answer 2

1. You haven't clarify either the numbers given will be sorted or not. If not, sort them, while will take O(nlogn).

2. Find upper bound of i, say x. Find lower bound of j, say y.

3. Now just check 4 numbers. Numbers at index x, x+1, y-1 and y. If any of the numbers of the given array is between i and j return true. Otherwise return false.

If the given Set/Array is not sorted, then in this approach additional O(nlogn) is required to sort it. Memory requires O(n). For each query, it's O(1).