问题标签 [rmq]

我被以下算法课的作业问题难住了：

假设给定一个包含 n 个值 x ₁ , x ₂ ... x _{n的序列，并寻求快速回答以下形式的重复查询：给定 i 和 j，找到 x i} ... x _j中的最小值

设计一个使用 O(n) 空间并在 O(log n) 时间内回答查询的数据结构。

首先，我不确定一个序列是指一个已排序的集合还是一个未排序的集合——但由于它没有说否则我会假设序列意味着未排序。

所以，我意识到这显然必须涉及二叉树，如果我们谈论的是 O(log N) 查找时间。所以基本上，我想，你有一个 set S，你将每个元素插入S到二叉树中。问题是，这个问题基本上是想让我想出一种方法来回答查询，其中我将一系列索引分配到一个未排序的集合中 - 然后在 O(log N) 时间内确定该范围内的最小值。这怎么可能？即使将集合的每个数字都插入到树中，我能做的最好的事情就是在 O(log N) 时间内查找任何特定数字。这不允许我在S.

有什么建议么？

我有坐标点 (x,y) 说我有 10 000 个点。现在当一个新点作为测试查询给出时说（p，q）。我必须检查坐标点中的每个点。如果文本查询的 x 坐标是来自在线搜索的 PY，我开始知道 Rmq-range min/max 查询数据结构可以帮助我，但我不知道该怎么做。有人能帮我怎么做吗..c ++中的任何参考或代码帮助都会有很大帮助.谢谢

我正在开发一个 Clojure 项目，该项目将数组作为输入，并在预处理和每个查询中找到每个、、、a的范围内的最小值。（预处理需要，但是通过使用并发（）并将数组划分为数组，我们可以解决这个问题）[i,j]ijO(n)O(1)O(n*log(n))pmapn/log nO(n)

因此，我选择将数组表示为向量，将矩阵表示为向量的向量。

这是 C# 中的功能之一：

这就是我在 Clojure 中编写它的方式：

首先，当我尝试运行它时，它向我显示了这个错误：

此外，我写的代码没有做我想做的事，因为我不知道如果并行工作，我该如何更改r（表示行号）的值。apply_fn即喜欢它在 c# 中的变化：

（r就像在 c# i中的-loop 中一样）for

提前致谢。

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

RMQ 的正式定义是：给定一个从有序集合（例如数字）中取出的对象数组，范围最小查询（或 RMQ） from to 询问子数组中最小元素的位置。

我不明白的是，为什么我们不能通过线性搜索来解决问题？在数组 A[0...n] 中，如果我们需要 RMQ(i,j)

在循环结束时，我们知道最小值和最小值所在的索引。

我肯定在这里遗漏了一些东西......有人可以帮我理解为什么我们需要RMQ吗？

我想知道为解决范围最小查询问题而制作的段树中有多少个节点。

另外，构建操作需要多长时间，为什么？

因此，我阅读了有关 RMQ（范围最小查询）的 TopCoder 教程，我遇到了一个大问题。

在他介绍方法的部分，到目前为止我能理解的是：

（整个方法实际上使用了稀疏表（ST）算法中引入的方法，从 LCA 到 RMQ以及从 RMQ 到 LCA的缩减）

给定一个数组 A[N]，我们需要将其转换为笛卡尔树，从而使 RMQ 问题成为 LCA（最低公共祖先）问题。稍后，我们可以得到数组 A 的简化版本，并使其成为受限 RMQ 问题。

所以它基本上是两个转换。所以第一个 RMQ 到 LCA 部分很简单。通过使用堆栈，我们可以在 O(n) 时间内进行转换，得到一个数组 T[N]，其中 T[i] 是元素 i 的父元素。树就完成了。

但这是我无法理解的。O(n) 方法需要一个数组 where |A[i] - A[i-1]| = 1，并且该数组在本教程的从 LCA 到 RMQ 的缩减部分中进行了介绍。这涉及到这棵树的欧拉之旅。但是，如何通过转换的最终结果来实现呢？我的方法不是线性的，所以在这种方法中应该被认为是不好的，线性方法是什么？

更新：让我感到困惑的一点

树的图片：

Euler Tour 需要知道每个节点的子节点，就像 DFS（深度优先搜索）一样，而 T[n] 只有每个元素的根，而不是子节点。

接我上一个问题“范围最小查询方法（从树到受限RMQ） ”（建议阅读）

同样，在 TopCoder 上的本教程中，我到处都有一些问题，我希望有人能解决它们。

因此，我将 RMQ（最小范围查询）问题转换为 LCA（最低公共祖先）问题，然后将其转换回来，我可以得到一个简化的数组。（两种变换都可以在教程中找到，简化的数组是“从LCA到RMQ”中讨论的数组L）

无论如何，我可以使用 Euler Tour 得到那个数组，这是所有计算的核心部分。

首先，我需要通过使整个数组仅包含 1 和 -1 来使其更简单，所以这就是我所做的Ls[i] = L[i] - L[i-1]：

第二步实际上是分区，这很简单，但是第三步让我感到困惑。

令 A'[i] 为 A 中第 i 个块的最小值，B[i] 为该最小值在 A 中的位置。

A指的是这句话中的L数组，所以最小值总是1或-1，并且会有多个1和-1。这让我很困惑，因为我认为这不会让计算变得更容易。

第四步，

现在，我们使用第 1 节中描述的 ST 算法对 A' 进行预处理。这将花费 O(N/l * log(N/l)) = O(N) 时间和空间。

如果 A' 只保留 1 和 -1 的记录，那么在上面做任何事情似乎都没用。

最后一步，

为了索引表 P，预处理 A 中每个块的类型并将其存储在数组 T[1, N/l] 中。块类型是通过将 -1 替换为 0 并将 +1 替换为 1 获得的二进制数。

这是什么意思？计算每种组合？比如000———— 001……？

它看起来像多个问题，但我希望有人可以引导我完成最后的这些步骤。谢谢！

继续我的最后两个问题，“最小范围查询方法（从树到受限 RMQ） ”和“最小范围查询方法（最后步骤） ”

我在 TopCoder 上遵循了本教程，该方法在最后一节中介绍。

现在假设我已经完成了所有工作，并且准备好进行查询。根据教程，这是我应该做的：

i 和 j 在同一个块中，所以我们使用在 P 和 T 中计算的值

例如，如果有这样的块：

最小值当然在第三个 0 中，但如果 i 和 j 像 4 和 6，则第三个 0 不会在查询条件中。我的理解错了吗？

i 和 j 位于不同的块中，因此我们计算三个值：使用 P 和 T 计算从 i 到 i 块末尾的最小值，使用对 A' 的预计算查询，计算 i 和 j 块之间的所有块的最小值，以及来自j的块开始到j，再次使用T和P；最后返回使用您刚刚计算的三个值的总体最小值的位置。

为什么要计算从 i 到 i 块末尾的最小值以及从 j 块开始到 j 的最小值？两者的答案不都在 i...j 之外吗？另外，如果它不像最后一个问题那样完全合适，该怎么做。

嗨，我正在尝试为 rmq-ing 实现 2D 范围树，这是我的代码，我认为它不够高效，有什么我可以做的优化。

ls 包含在每个节点上排序的 y 列表

rt 包含一个段树

p.fi.fi 包含 x 坐标

p.fi.se 包含 y 坐标

p.se 包含点的 id

loc 包含每个 id 的 x 节点和 y 节点

如果代码是一团糟，我很抱歉，因为这是我第一次实现范围树

我当前的实现运行了大约 4 秒，但我需要它运行不到 3 秒，这是我的完整 实现

谢谢 ：）

我有一个包含 10 个数字的数组 supprse A[10] = {1,2,3,4,5,6,7,8,9,10} 我必须计算特定范围内的数字相乘但没有得到正确答案，我使用的是段树，不知道如何使用查询操作这是我的代码：