范围最小查询基础

Question

我阅读范围最小查询维基百科的链接，看着一对夫妇更教程（TopCoder公司等各个环节），但我有一个非常基本的问题：

RMQ的正式definitino是： 给定一个从排序良好的集合（例如数字）中取出对象的数组，从最小查询（或最小查询）（或RMQ）开始，查询子数组中最小元素的位置。

我不明白的是为什么我们不能通过线性搜索来解决问题呢？ 在阵列A [0 ... n]的，如果我们需要RMQ（I，J）

min = A[i] 
index = i 
for iter=i; iter <j; iter ++ 
if A[iter] <= min 
min = A[iter] 
index = iter; 

由循环的结尾，我们知道的最小和的索引，其中分钟所在。

我绝对错过了这里的东西......有人可以帮我理解为什么我们需要RMQ吗？

Answer 1

RMQ旨在解决您描述的问题，但方式更快。有两种方法 - 一种静态版本，您可以在其中进行一些预计算（最优化的版本非常复杂，需要进行线性预计算），然后对每个查询持续进行答案，并在每个查询的日志（n）时间进行动态报告。

在静态情况下，您不能更改初始数组，而在动态中允许其值随时间变化。

请注意，在这两种情况下，您都想回答很多问题。这意味着以恒定或对数时间进行回答会比直线方式更快，因此在您的想法过于缓慢的情况下可以发挥作用。希望这解释了这个想法。

Answer 2

速度。线性搜索速度很慢。

我们使用quick sort（或合并排序，...）而不是天真的insertion sort排序大型数据库的原因相同。

假设您拥有庞大的数据库，并且您将要查询RMQ数百万次。对每个查询的线性搜索效率不高，需要数百万的线性搜索，而更高级的算法需要较小的预处理，然后快速检索所需的信息。