从未排序数组中获取最大值

Question

我有一个未排序数组。我有很多查询，我给了一个范围（表示为两个数组索引），然后从该范围（即，从数组的指定切片）的最大值必须返回。 例如：

array[]={23,17,9,45,78,2,4,6,90,1}; 
query(both inclusive): 2 6 
answer: 78 

哪个算法或数据结构我构建快速检索从任意范围的最大值。 （有很多的查询）

编辑： 我使用C++

Answer 1

我认为一些预处理是允许的。它是范围最小查询问题（这里最大）。 Good review of this problem at TopCoder。 合适的数据结构：段树和Sqrt-decomposition

Answer 2

归并ň得到的范围内的最后一个索引值将我最大。

array [] = {23,17,9,45,78,2,4,6,90,1}; 查询（包括两端）：2 6

归并返回第6指数VAR（指数= 1个.. N）

答案：78

Answer 3

让我们说这是你的阵列array[]={23,17,9,45,78,2,4,6,90,1};

如果阵列并不大，我会为您提供阵列预处理，并得到另一个数组这样的：

{0,0} = 23; //between arr[0] and arr[0] 
{0,1} = 23; 
{0,2} = 23; 
{0,3} = 45; 

{9,9} = 1; 

所以你的新阵列将是newArr = {23,23,23,45,....., 1}

你可以找到为O搜索（1），例如，4-5之间最大的newArr[4*array.length+5)-1]; 总共，对于n个查询，您将拥有O（n）。

的空间，如果你有10000（10^4）整数，那么你的newArr = 10^8 * 4B = 400MB，所以如果你有超过10000 INT，那么这难道不工作

编辑：我想到了一些东西，但它与algorithm in Topcoder相同，即MBo提及。