algorithm - 范围最小查询基础知识

Question

我阅读了 Range Minimum Queries 上的维基百科链接，查看了更多教程(topcoder 和其他链接)，但我有一个非常基本的问题:

RMQ 的正式定义是:给定一个从有序集合(例如数字)中获取的对象数组，一个范围最小查询(或 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 旨在解决您描述的问题，但比您的方法要快得多。有两种方法 - 静态版本，您可以在其中进行一些预计算(真正复杂的最优化版本需要线性预计算)，然后不断回答每个查询，以及动态方法，其中每个查询都有 log(n) 时间。

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

请注意，在这两种情况下，您都需要回答很多问题。这意味着以常数或对数时间回答比线性方法快得多，因此在您的想法太慢的情况下也能奏效。希望这能解释这个想法。