我是一个算法类难倒以下的家庭作业问题：

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

假设我们有一个序列   ñ值x 1 ，X 2 ... X N ，并寻求对   快速回答反复查询   形式：给定i和j，找到最小   以x 值i ... X Ĵ

Suppose that we are given a sequence of n values x1, x2 ... xn, and seek to quickly answer repeated queries of the form: given i and j, find the smallest value in xi... xj

设计一个用0-1的数据结构（N）   在O空间和答案的查询（log n）的   时间。

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.

所以，我明白，这显然必须涉及一个二叉树，如果我们谈论的是为O（log N）的查找时间。所以基本上，我想，你有一组取值，你插入取值的每个元素转换成二进制树。问题是，这个问题基本上要我想出了一个办法回答疑问的地方，我给出一个索引范围到的未分类的设置 - 然后确定在此范围内为O的最低值（日志N）的时间。这怎么可能？即使集合中的每个数字被插入到树，最好的，我能做的就是查找为O任何特定数目（日志N）的时间。这并不让我找到号码的未排序范围的最低值取值。

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.

有什么建议？

推荐答案

OK，我想我有一个良好的开端为你，我学会了在这个过程中一些新的东西。

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!