问题标签 [rmq]

我的作业有问题，需要我解决类似于 range-minimum-query 的问题。问题大致描述如下：

我应该编写一个 java 程序，它读取大量整数（大约 100,000）并将它们存储到一些数据结构中。然后，我的程序必须回答给定范围 [i,j] 中的最小数字的查询。我已经成功地设计了一种算法来解决这个问题。但是，它还不够快。

我的算法的伪代码如下：

有人可以告诉我我能做什么，以便我的算法足够快来解决这个问题吗？

可以在此链接中找到分配文件：http: //bit.ly/1bTfFKa

我已经被这个问题难住了好几天。任何帮助将非常感激。谢谢。

我知道 BIT 是如何工作的。但我想知道是否可以使用 BIT 来查找完整范围内的最小/最大值元素，或者更具体地说，在所有更新过程完成后查找最小值（或最大值）。现在，我知道使用段树可以很好地实现这一点，但是使用 BIT 可以做到这一点吗？

谢谢。

PS：我知道遍历完整BIT并计算每个索引的值的明显方法。我正在寻找一种更有效/优化的方式。

我知道如何在 O(n) 时间内将数组转换为笛卡尔树

1. http://en.wikipedia.org/wiki/Cartesian_tree#Efficient_construction和
2. http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor#从 RMQ 到 LCA

但是，所需的内存量太高（常量），因为我需要至少将左右指针与笛卡尔树中的每个节点相关联。

任何人都可以将我与减少这些常数的工作联系起来（希望减少到 1）吗？

我进行了演示测试，结果得分为 62。我猜我的代码效率不足以达到最高分 100。那么如何有效地找到子字符串中的最低字符代码？例如，字符串是s="ACGTTAGTAC". 有效地找出子字符串中的最小字符是什么s[p,q]- 有许多重复的查询具有相同s但不同的[p,q]. 实际上，这个问题被称为范围最小查询（RMQ），并且有不止一种算法可以解决这个问题。但是我很难理解并将它们应用于这个特定的实例。谁能建议如何修复代码？

由于版权问题，完整的问题没有复制到这里。您可以从此链接https://codility.com/demo/results/demoHSB3XQ-R24/阅读完整的详细信息。

形式上，范围最小查询问题是：

给定一个数组 A[0, N-1] ，找到任意两个给定索引之间具有最小值的元素的位置。

现在，标准解决方案是使用分段树，并在此处进行了描述。另一种用于解决范围查询的数据结构是二叉索引树（Fenwick Tree），它更容易理解和编码。

Binary-Indexed-Trees 可以解决范围最小查询问题吗？如何解决？更新和查询功能的实现将不胜感激。

我在数据结构课程中进行了测试，其中一个问题是：

假设您有一个 n 大小的数组，该数组由 Range Minimum Query 维护，该查询给出了 o(1) 复杂度的数组中两个数字之间的最小值。当然，该数组是 o(n) 准备使用动态编程针对不同选项来回答 RMQ 的。问题是 - 如果我更改数组中的一个对象（数字），我将如何更改我所做的准备工作以便我仍然可以在 o(1) 中找到 RMQ，以及它需要什么复杂性。

答案不是在 o(n) 中创建一个新的 RMQ，它必须小于这个值。

这个问题不是作业，我只是想通过测试来理解。

提前致谢。

我正在尝试开始使用 RMQ，但在创建我的应用程序时出现此错误。我按照安装 gem 然后创建项目的说明进行操作。我应该从哪里得到必要rmq-template的东西？

我应该怎么做？

我在Codechef March Long Contest的问题GCD 条件中获得 WA 。 请告诉我我做错了什么或代码产生错误答案的一些测试用例。

问题链接

我对每个素数都使用了 RMQ（范围最大查询）

首先，我已转换为如下结构：-

示例输入：- 10 6 20 15 8

(b[i]-->存储 i 的因子的索引)

b[2]--> 1,2,3,5
b[3]--> 2,4
b [5]--> 1,3,4


现在实现RMQ后，如下：-

(cc[i][j][k] 存储 b[i][j] 和 b[i][j+(2^k)-1] 之间最大元素的索引)

cc[2][0]-- >1,2,3,5
cc[2][1]-->1,3,3
cc[2][2]-->3

cc[3][0]-->2,4
cc[3][1]-->4

cc[5][0]-->1,3,4
cc[5][1]-->3

我的代码

我正在尝试为表格中的每个单元格创建一个切换按钮。按下时，它将更改图像，再次按下时将再次更改图像 - 切换。

在UIButton课堂上我没有看到一个selected状态。

我正在寻找一种使用 UIButton 创建切换按钮的方法，以便我可以在每次单击时更改状态。

这就是我rubymotion现在使用的方式rmq

我想要UIViews 的默认样式。

假设我想要 ALLUILabel和backgroundColorof color.light_gray。
此外，我想为我的自定义设置样式UIView，例如对于AttributedUILabel我想要将kerning值设置为的每个2。

如何在 RMQ 中解决这个问题？