algorithm - 查找子序列的最小元素

Question

给定一个整数元素序列S，我需要一个函数来找到索引 i 和索引 j （包括两者）之间的序列的最小元素，使得：nmin(i,j)

1. 初始化需要O(n);
2. 内存空间O(n)；
3. min(i,j)需要O(log(n)).

请为此提出一个算法。

Answer 1

Segmenttree 就是您所需要的，因为它满足您的所有要求。

1. 使用段树初始化需要 O(n)
2. 内存也是 O(n)
3. 查询可以在 O(log n) 中完成

除此之外，树是动态的，可以支持 O(log n) 的更新。这意味着可以在 O(log n) 中修改某个元素 i 的元素，并且仍然可以检索最小值。

Answer 2

此 TopCoder 教程：< O(n), O(1) > 方法更详细地讨论了您的问题。在符号中，意味着该方法需要 f(n) 复杂度来设置，以及 g(n) 复杂度来查询。

此外，这篇文章再次咀嚼算法：范围最小查询 <O(n), O(1)> 方法（从树到受限 RMQ）。

希望他们澄清你的问题:)

Answer 3

段树正是您所需要的（它可以及时构建O(n)，一个查询需要O(log n)时间）。这是一篇关于它的文章：http ://wcipeg.com/wiki/Segment_tree 。
即使有一种算法使用O(n)时间进行初始化和O(1)每次查询的时间，段树也是一个不错的选择，因为它更简单。