在列表中查找所有可能子范围的最小值的算法

Question

假设我有一个列表:

L = [2,5,1,8,3,7,9,4,6,10]或类似的东西

而且我希望能够创建一个二维列表/数组/等来描述所有可能范围的最小值(例如，最小值[0][3] 表示查看元素 0 到 3 时的最小值)。

例如:

Range(0 through 3) = minimum is 1
Range(5 through 5) = minimum is 7
Range(3 through 8) = minimum is 3

等等，对于所有可能的范围。有没有比 n^2 次更好的方法？

Answer 1

为它建立一个线段树。查询时间为 O(logn)。 http://en.wikipedia.org/wiki/Segment_tree