假设我们有大量的整数A.我们想回答许多查询,例如：
>在索引0到100之间找到最小值
>在索引4和90之间找到最小值
> …
示例：A = {6,1,7,5,3}
>索引0和1之间的最小值为1
>索引2和3之间的最小值是5
>索引0和4之间的最小值为1
对于性能而言,遍历每个查询的元素并查找最小值的明显方法还不够.我需要以某种方式存储所需的信息,然后在固定时间内回答查询.因此,算法不应为二次方.需要比O(N * M)更好的东西. (N：数组大小,M：查询数)
我尝试过,但找不到解决方法.它一定是关于寻找和存储一些和以某种方式使用它们的东西.有任何想法吗？谢谢阅读.
最佳答案
要考虑的两个选项：
> O(n)预计算和每个查询的O(logn)
> O(nlogn)预计算和每个查询O(1)
第一个通过递归计算偶数位置上所有对的最小值,然后在4的倍数上的所有4处递归计算最小值,然后在8的所有倍数上的所有8进行递归计算.然后,每当您要访问特定范围的最小值时,便将其分解为已有的部分并计算其中的最小值.
例如,要查找元素1..10的最小值,请使用元素1和2..3以及4..7和8..9和10的最小值.
第二种方法是计算所有位置上所有对的最小值,然后计算所有位置上的所有4,然后计算所有位置上的所有8.当您具有特定范围时,可以将其构造为两个部分中的最小值,然后计算这两个部分中的最小值.
例如,请使用元素1..8的最小值和元素3..10的最小值.