從未排序數組中獲取最大值

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提及。