What data structure using O(n) storage with O(log n) query time should I use for Range Minimum Queries?

Question

I'm stumped by the following homework question for an algorithms class:

Suppose that we are given a sequence of n values x₁, x₂ ... x_n, and seek to quickly answer repeated queries of the form: given i and j, find the smallest value in x_i... x_j

Design a data structure that uses O(n) space and answers queries in O(log n) time.

Firstly, I'm uncertain whether a sequence refers to a sorted set, or an unsorted set - but since it doesn't say otherwise I'll assume sequence means unsorted.

So, I realize this obviously must involve a binary tree, if we're talking about O(log N) lookup time. So basically, I figure, you have a set S, and you insert each element in S into a binary tree. The problem is, the question basically wants me to come up with a way to answer queries where I'm given a range of indices into an unsorted set - and then determine the lowest value in that range in O(log N) time. How is that possible? Even if each number of the set is inserted into the tree, the best I can do is lookup any particular number in O(log N) time. This doesn't allow me to find the lowest value in an unsorted range of numbers in S.

Any suggestions?

Answer 1

OK, I think I have a good start for you, and I learned something new in the process.

I would take a look at the Wikipedia entry on Cartesian trees. I'm not going to tell you more than that for fear of doing your homework for you, but you seem like a smart guy so I figure you can work it out.

Thanks for helping me learn a new data structure, by the way!