我对算法类的以下作业问题感到难过:
假设我们给出了一个n值x 1,x 2 ... x n的序列,并寻求快速回答形式的重复查询:给定i和j,找到x i ... x j中的最小值
设计一个使用O(n)空间的数据结构,并在O(log n)时间内回答查询.
首先,我不确定一个序列是指一个有序集合,还是一个未排序的集合 - 但由于它没有说明,否则我会假设序列意味着未排序.
所以,我意识到这显然必须涉及二叉树,如果我们谈论的是O(log N)查找时间.所以基本上,我想,你有一个集合S,并将每个元素插入S到二叉树中.问题是,这个问题基本上要求我想出一种方法来回答查询,其中我将一系列索引分配到未排序的集合中 - 然后在O(log N)时间内确定该范围中的最低值.怎么可能？即使将每个数量的集合插入树中,我能做的最好的事情是在O(log N)时间内查找任何特定的数字.这不允许我在未排序的数字范围内找到最低值S.
有什么建议？