相关疑难解决方法(0)

排序和有序集合之间有什么区别吗？

我正在审核这个算法类的工作,我正在尝试做一些在课堂上给出的练习题.这个问题让我感到难过,我无法绕过它.我的解决方案都没有在O(logn)时间内出现.任何人都可以帮我解决这个问题吗？

问题:假设我们以任意顺序给出n个值x1,x2,...,xn的序列,并寻求快速回答形式的重复查询:给定任意对i和j,其中1≤i<j≤ n,找到x1,...,xj中的最小值.设计一个使用O(n)空间的数据结构,并在O(log n)时间内回答每个查询.