求一种快速指定区间内最大值的算法~

如题……有一组数字

编号 ： 1 2 3 4 5 6 7 8 9
值  ：    9 7 5 6 3 1 2 8 4

例如求闭区间

[3,7]的最大值为6

[4,8]的最大值为8

那么有没有一种时间复杂度少于o(n)的算法能快速得出结果?~

PS:目前想到用二维数组,运算速度虽然很快……不过大数据运算空间开销太大了……或者有一种算法能够实现空间和时间开销都不怎么大的算法~

欢迎讨论~

[此贴子已经被作者于2017-10-30 11:11编辑过]