在陣列單變化的複雜性保持了靜態範圍最小查詢

Question

我曾在數據結構課程的測試和是一個問題：

可以說你有一個正大小的數組是保持用範圍最小查詢給出了o（1）複雜度中數組中兩個數之間的最小值。 當然，陣列是o（n）準備回答RMQ使用動態編程爲不同的選項。 問題是 - 如果我更改數組中的一個對象（數字），我將如何更改我所做的準備，以便我仍然可以在o（1）中找到RMQ，以及需要什麼複雜度。

答案是不在o（n）中創建一個新的RMQ，它必須小於這個值。

這個問題不是作業，我只是想通過測試來了解。

在此先感謝。

Answer 1

存儲索引I和元素的新值V改變。

在得到一個查詢[L，R]，檢查如果L < = I < = R，如果這樣返回old_rmq（L，R）和V的最低

Answer 2

實際上有三種類型的基礎上，複雜性和update爲query算法RMQ：

Update  Query 
1. O(N)  O(1) 
2. O(1)  O(N) 
3. O(logN) O(logN) 

第一和第二類型的算法是非常容易實現。第一個涉及存儲所有可能的查詢的值，從而在O(1)時間內回答它們。第二個涉及只更新O(1)時間的數據結構，但查詢需要O(N)。根據你的問題，你不可能有這樣的組合。

然而，第三種類型的算法是特別感興趣的。如果放寬查詢可能需要O(logN)時間的條件，而不是O(1)，那麼無論更新和查詢的數量如何，您都可以在總體運行時間保持不變的情況下獲得優勢。

AFAIK，用於獲取這樣的運行時間最佳的數據結構是Segment tree和Binary Indexed Trees