问题标签 [rmq]

A假设我有一个长度为整数的数组N，我也有一个整数L<= N。

我试图找到的是范围 [0, L-1], [1,L], [2,L+1]....[NL,N-1] 的最小值

L（就像一个从左到右移动长度的窗口）

我的算法现在是 O(N lg N) 和 O(N lg N) 预处理：

1. 将所有号码保存A[0...L-1]在多组S中，并将号码按顺序存储在队列Q中。[0, L-1] 的最小值只是 的第一个元素S。O(N lg N)
2. 弹出 的第一个元素Q，在里面找到这个元素S并删除。然后推A[L]入S。[1, L] 的最小值只是 的第一个元素S。O(lg N)
3. 对所有可能的范围重复步骤 2，每次迭代移动到下一个元素。上）

总计为 O(N lg N)。

我想知道是否有任何算法可以达到比这更好的以下要求：

1. 预处理时间（如果需要）为 O(N)
2. 查询时间如果 O(1)

我对 RMQ 进行了一些研究，我发现最近的方法是使用稀疏表，它实现 O(1) 查询时间但 O(N lg N) 预处理时间。另一种将RMQ简化为LCA问题的方法可以满足要求，但需要对数组进行一些限制A。

那么在解决我的问题时，是否有可能在没有限制A的情况下满足要求？

根据这篇论文，我发现使用两个 BIT 来做 RMQ 非常棒O(lg N)，因为它比分段树更容易编码，并且论文声称它的性能也优于其他数据结构。

我了解如何构建树以及如何进行查询操作，但我对更新操作感到困惑。这是报价单：

我们进行以下观察：当我们生成我们经过的节点的关联区间时，我们可以通过从节点 p + 1 开始并爬上第一棵树来覆盖整个区间[ p + 1, y ] （图 2.1）。因此，我们不是对我们更新的每个节点都进行查询，而是通过爬树一次来动态计算查询的结果。

类似地，我们可以通过从节点 p – 1 开始并爬上第二棵树来更新[ x, p – 1]形式的所有区间（图 2.2）。相同的算法适用于更新两棵树。

我怀疑应该反过来：为了找到区间[p+1, y]的最小值，我们应该使用第二棵树而不是第一棵树；为了找到区间[x, p-1] 的最小值，我们应该使用第一棵树。

我的问题是：我是对的吗？如果不是，有人可以举一个简单的例子来演示更新操作是如何工作的吗？

我试图解决一个非常基本的问题，它只涉及 Range Minimum Query 的实现。问题的链接是

https://www.hackerearth.com/practice/data-structures/advanced-data-structures/segment-trees/tutorial/

但是我超过了时间限制。请有人帮助调试我的代码。

提前致谢

我正在尝试通过https://www.topcoder.com/community/data-science/data-science-tutorials/range-minimum-query-and-lowest-common-ancestor/ 了解段的基础知识后学习段树树 我试图解决这个问题。但是只有一个测试用例通过了，而在第二个测试用例上，我开始感到厌烦了。在进一步检查使用 filediff 比较两个答案时，我发现有错误的答案。我找不到任何错误。请帮忙。

此代码用于创建和更新段树。

变量 - 节点 = 段树中的起始索引，即 1。b = 下限，e = 上限

现在，此代码用于从树中查询最小索引。

这用于更新原始数组中的索引。

我正在使用来自第一个索引的段数组。完整代码参考这里

现在我已经更改了一些代码，以防万一从这里看到后发生更新，但现在我得到了错误的答案-：

有关更新的完整代码，请参阅此处

https://www.hackerearth.com/practice/data-structures/advanced-data-structures/segment-trees/practice-problems/algorithm/range-minimum-query/description/

我正在尝试解决这个问题。我正在制作 Math.ceil(Math.sqrt(arrSize)) 的矢量大小。我使用了以下方法 - 用于构建 sqrt 向量

我正在取平方根块并在块中找到最小的索引并将它们存储在 vect 数组中。

如何从 Sqrt(n) 提高更新查询的复杂性。

使用本教程-：http ://www.geeksforgeeks.org/sqrt-square-root-decomposition-technique-set-1-introduction/

我正在使用以下算法（伪代码）执行任务

循环试图做的是，使用先前计算的范围A[j]来计算 current A[i]。

对我来说，这就像做 N 个动态 RMQ（范围最小查询）。

它是动态的，因为我们事先不知道 的值A，我们使用先前计算的值在线计算它。

例如，

所以我的问题是，有没有比O(N^2)实现这个更快的算法？我觉得有一些方法/数据结构可以加速NRMQ，但我不知道如何。

如果示例不清楚，请告诉我详细说明。

我需要一种在 Python 中具有一些数据结构的算法，在每一步给出两个新元素 e1、e2 时：

• 查找第一个和第二个给定元素的插入位置（保持顺序）.
• 在两个插入位置之间的间隔中找到元素的最大值。
• 在第二个给定元素的先前找到的插入位置插入，第二个给定元素与在区间中找到的最大值加上一个常数配对。除非第二个给定元素已经存在，在这种情况下，如果新值更大，我们只需要更新它的值。

并且此步骤必须在不超过对数时间内完成，因为当此步骤重复 N 次时，整个最坏情况的时间复杂度不会远离 O(NlogN)。

-- 例如：my_list = [(2,1), (4,3), (5,7), (9,1)]

如我们所见，元素 2 与其分配的值 1 配对，元素 4 与值 3 配对，5 与值 7 配对，9 与值 1 配对。并且 my_list 由对的第一个元素排序。

现在，给出了两个元素，e1 = 3，e2 = 6。

(e1, ) == (3, ) 在 my_list 中的插入位置为索引 1，(6, ) 的插入位置为索引 3。

在 my_list 的索引 1 和 3 之间的元素中找到的最大值是值 7，因为 (4,3)、(5,7) 的最大值是 7。

假设要添加的常数是 1，我们有：找到最大值 + 常数 == 7 + 1 == 8。我们有 e2 == 6，所以要插入的对是索引 3 处的 (6, 8)。

在这一步结束时，my_list 必须是：[(2,1), (4,3), (5,7), (6,8), (9,1)]

- 这里链接的这个问题非常相似，但与我关于插入元素的索引的问题不同。在那个问题中，元素被添加到最后（附加），在我的情况下，插入必须以保留元素顺序的方式完成，以便可以在对数时间内找到下一个任意间隔的开始和结束. 这就是为什么我认为，除了使用范围最小查询之外，我还需要使用一些高级数据结构，例如区间树或树形图。

给定一个包含 n 个元素的数组。找到范围 [l...r] 中元素的最小值，使得 a[k]> p 。（ l<=k<=r 和 p 随 l 和 r 而变化）。

有没有适用于 log(N) 的解决方案？

这是我运行 main 时遇到的错误。我真的不明白为什么第 44 行有问题：channel.basicConsume(Q,true,consumer); 我的目标是尝试将收到的消息存储到我可以在其他文件中使用的变量中。

这是我的 Recv 文件代码

我试图解决如何在给定的数组和两个索引中找到 O(Log(n)) 中这两个索引之间的最小值。我看到了使用段树的解决方案，但不明白为什么这个解决方案的时间复杂度是 O(Logn)，因为它看起来不像这样，因为如果你的范围不完全在节点的范围内，你需要开始拆分搜索。