问题标签 [rmq]

我有 N 个整数 Ai 定义为 A1, A2, ..., AN。我必须处理表格 a 的 Q 查询。对于每个这样的查询，找到一个索引 i 使得 Ai ≥ a。我必须尽量减少 Ai-a 的差异。我已经做到了

但这会导致 TLE 。有效的方法是什么？

我有一个兔子 mq 服务器正在运行，我的所有消息都通过一个直接交换。消息被路由到各个非永久队列（它们可能会持续几个小时）。我刚开始阅读有关队列绑定到交换的内容，并且对于我是否真的需要将队列绑定到交换有点困惑。我正在使用pika basic_publish和consume函数，所以也许这是暗示的？不太确定只是想了解更多。

谢谢

输入是一个数组(n*m 1<n,m< 1000)。我必须在 的每个子矩阵中找到最大元素size( a*b )。

我试图通过x一遍n-a+1又一y遍地迭代来做到这一点m-j+1。

• 2D segment treesor quad trees不够快，因为查询的数量很大。

• 我试图扩展sparse table，但由于空间不足而无法扩展。

• 我已经阅读了有关解决方案的信息，Cartesian trees但是由于我无法理解，因此需要一些代码。

请解释一个将通过预计算O(nm)及时或及时回答查询的解决方案。O(1)此外，输入数组是静态的。

注意：虽然我试过sparse table了，但它可能不正确，所以请随时发布解决方案。

我是一名Java编码员，所以实现Java或c/c++将是伟大的。

这也不是重复的，因为我已经搜索了很多关于它没有找到任何合适的东西。

我正在尝试添加RMQClient framework到我的XCODE 7.3项目中。我正在按照https://github.com/rabbitmq/rabbitmq-objc-client以及RabbitMQ官方网站中指定的步骤进行操作。

添加框架并运行后，Tools->Build我收到

错误消息并且无法从框架中导入任何头文件。对这个问题有什么建议吗？

我有一个将消息提交到远程RMQ服务器上的交换的 Objective C 提供程序。我有一个消费者正在监听绑定到该交换的队列。我正在使用扇出。当从 Xcode 运行应用程序一切正常时，消息被发送，消费者接收它。

但是，当从 iPhone 设备运行应用程序时，消息不会显示在管道的末端。

这是我的发送方法：

我有一个大小为 1 的数组说 A(0 indexed)。

我想在索引 k1 (k1>=0) 和 A.size()-1（即最后一个元素）之间的数组 A 中找到最小值。

然后我将在数组末尾插入值：（给定范围内的最小元素+一些“随机”常量）。然后我有另一个查询来查找索引k2和A.size（）-1之间的最小值。我发现，在最后插入值：（给定范围内的最小值+另一个“随机”常量）。我必须做很多这样的查询。

说，我有 N 个查询。天真的方法需要 O(N^2)。

不能使用段树，因为数组不是静态的。但是，一个聪明的方法是为大小为 N+1 的数组制作段树；事先并用无穷大填充未知值。这会给我 O(Nlog N) 的复杂性。

NlogN 复杂度甚至 N 有没有其他方法？

我在段树的延迟传播中面临一个问题。我有一个数组A，长度为 N ，较小的数组（最大长度为 20）。我还有一个索引数组B ，指的是我当前在数组Ai中指向的索引。

有 2 个操作，： a) 更新B的指针以指向给定范围的下一个元素。b) 打印给定范围内指针当前指向的最大值。

例如：-

在查询范围 1,2 时，最大值为 8。这是因为数组 B 的指针指向数组的第一个元素。所以我们正在使用 1,8。

在进行 2,3 max =8 的查询时；这是因为我们正在使用值 8,3。一般来说，

这是非常简单的两种方法。但是，由于输入限制较大，我需要 O(logn) 查询和更新时间。这就是为什么我想到使用段树的原因（目前它的复杂性是 O(n^2)。但是我似乎无法弄清楚如何更新延迟传播中的中间节点。

任何见解都会有所帮助。另外，如果您可以在线链接任何类似的问题，那将非常有帮助，因为我做不到（我不知道这样的问题不是来自任何网站）。感谢您的任何帮助。

注意：如果b[i]>a[i].length然后替换a[i][b[i]]为 1。

我正在解决的问题的一部分涉及在数组（RMQ）的范围内获得最小值，所以我实现了一个段树，到目前为止它工作正常。然后我想更新原始数组中的一项（没有超过一项的更新）并在段树中更新它。到目前为止，我所做的是从上到下遍历线段树，直到到达叶子，但这似乎有一些错误。这是代码的更新部分，那里似乎有什么问题？

PS n 不是 2 的倍数（我不知道这是否会影响解决方案）

PS问题的其他部分可能有一些bug，但似乎这是最有可能出现bug的部分。

我正在查看Range minimum queries。

维基百科说：

长度为 n 的数组有 Θ(n²) 可能的查询。

我不明白这个。这是一个大小为 5 的数组的示例
。可以进行以下查询：

1 个查询 [0,4]
2 个查询 [0,3] 和 [1,4]
3 个查询 [0,2],[1,3] 和 [2,4]
4 个查询 [0,1],[1, 2]、[2,3] 和 [3,4]
5 个查询 [0]、[1]、[2]、[3] 和 [4]

可能的查询总数

[0,4] +
[0,3] + [1,4] +
[0,2] + [1,3] + [2,4] +
[0,1] +[1,2] + [2 ,3] + [3,4] +
[0] + [1] + [2] + [3] + [4]

---------------------------------
15 个查询

但我期待N^2 = 25查询（其中 N 是数组大小 = 5）

我错过了什么？谁能解释一下？

我正在尝试构建用于执行 RMQ 的段树。不知何故，无论我查询什么范围，它都会返回 0。

例如，我的数组是[ 1,2,3,4,5,6,7,8,9,10 ]. 从索引 3 到 5 的 RMQ 应该给出 4。但我的代码一直输出 0。

我的代码：

编辑：

感谢所有的帮助。就像下面提到的答案一样，我的查询范围是错误的。除此之外还有2个错误：

if(lo <= a && hi >= b)应该(a <= lo && b >= hi)

和

return st[r] = min(query(r<<1,lo,mid,a,mid),query((r<<1)|1,mid+1,hi,mid+1,b));

应该

return min(query(r<<1,lo,mid,a,mid),query((r<<1)|1,mid+1,hi,mid+1,b));

因为我只是进行查询而不应该修改树。