c++ - 范围内的最低值

Question

我想找到某个范围内的最低值。
是每次都要遍历数组还是有什么动态方法？

假设我有输入数组:

index: 0 1 2 3 4 5 6 7
value: 1 4 6 1 6 7 2 3

然后我必须选择 (含)范围内的最小值。例如:

min(0,7) = 1
min(0,2) = 1
min(4,6) = 2
min(1,2) = 4

我对最快的解决方案感兴趣，最好在恒定时间内获得结果。

Array 不会同时改变。

Answer 1

如果您要对同一组数字执行多个查询，那么您需要构造一个 Cartesian Tree .

Cartesian trees may be used as part of an efficient data structure for range minimum queries, a range searching problem involving queries that ask for the minimum value in a contiguous subsequence of the original sequence.

正如文章所说，查询可以在恒定时间内执行。