查找給定序列<code>n</code>的<code>S</code>整數元素的子序列

Question

的最小元素，我需要一個函數min(i,j)，用於查找索引之間的序列的最小元素i和索引j（包括兩端），使得：

1. 初始化需要O(n);
2. 存儲空間O(n);
3. min(i,j)需要O(log(n))。

請爲此提出一個算法。

Answer 1

Segmenttree是您需要的，因爲它滿足您的所有要求。

1. 初始化需要用線段樹
2. 內存爲O（n）也爲O（n）
3. 查詢可以在O（log n）的

這旁邊做了，樹動態的，並且可以支持O（log n）中的更新。這意味着可以修改O（log n）中的某個元素i的元素，並仍然檢索最小值。

Answer 2

此TopCoder教程：An < O(n), O(1) > approach更詳細地討論您的問題。在符號中，意味着該方法需要f（n）設置的複雜性，以及g（n）的複雜性來查詢。

另外，這篇文章再次咀嚼算法：Range Minimum Query <O(n), O(1)> approach (from tree to restricted RMQ)。

希望他們明確你的問題:)

Answer 3

段樹就是你所需要的（也可以建立O(n)時間和一個查詢需要O(log n)時間）。 這是一篇關於它的文章：http://wcipeg.com/wiki/Segment_tree。
即使有一個算法使用O(n)時間進行初始化，每個查詢使用O(1)時間，但分段樹可能是一個不錯的選擇，因爲它更簡單。