Designing a data structure that works in O (logn) time

Question

I am checking this class of algorithms for work, and I am trying to make some practical problems posed in the class. This problem puzzled me, and I just can not hug her around. None of my solutions go to O (logn). Can someone help me with this problem?

Question: Suppose we are given a sequence of n values ​​x1, x2, ..., xn in an arbitrary order and strive to quickly respond to repeated requests of the form: if you specify an arbitrary pair i and j with 1 ≤ i <j ≤ n, the smallest value in x1, ..., xj. Create a data structure that uses O (n) space and responds to every request in O (log n).

Answer 1

To enter a1, a2, a3, ... an, construct a node that contains a minimum (a1, ..., ak) and a minimum (ak + 1, ..., an), where k = n / 2.

Recursively build the rest of the tree.

Now, if you want to find the minimum between ai and aj:

• Identify the smallest common ancestor i, j. Let it be k
• Start with me and keep moving until you press k. At each iteration, check to see if the child node node remains. If yes, then compare the correct min subtree and update the current min accordingly.
• Similarly, for j, check if this node value is correct ....
• In node k, compare the values ​​returned by each subtree and return min

Answer 2

People think about it. Suppose you start with a list:

47, 13, 55, 29, 56, 9, 17, 48, 69, 15 

Make the following list of listings:

 47, 13, 55, 29, 56, 9, 17, 48, 69, 15 13, 29, 9, 17, 15 13, 9, 15 9, 15 9 

I leave the construction of these lists, the correct use and proof that they provide an answer to the original question as exercises for the reader. (This may not be homework for you, but it may be easy for someone, and I don't like giving complete answers to homework.)

Answer 3

I think the decisive step is that you will need to sort the data before you start. Then you can save the data in an array / list. Then you can run a quick binary search in O (logn) by selecting the first value that satisfies the condition (I assume you meant between xi and xj, not x1 and xj).

edit: with a second thought, ensuring that the value satisfies the condition may not be as trivial as I thought

Answer 4

The question was asked a little differently: What data structure using an O (n) storage with O (log n) output time should be used for minimum Range queries?

However, to quickly answer, the problem you are facing is well understood - Minimum range query. The segment tree is a data structure that can solve the problem with the requirements of time O (N) and O (logN). You can see more details in here , where there is an explanation of the structure and the associated difficulties.

Answer 5

Trying to explain the proposed data structure:

For each pair of numbers, calculate and save a smaller value. For every four consecutive numbers, calculate and store the value of the smallest of the four. This is done quickly by choosing the smaller of the two values ​​of the pair. For every eight consecutive numbers, calculate and save the value of the smallest of the eight. And so on.

Say we want to get the smallest value from x19 to x65.

We will consider the following saved values: The smallest from x32 to x63. The smallest from x24 to x31. The smallest from x20 to x23. x19. The smallest from x64 to x65.

Then we select the smallest of them.