问题标签 [range-query]

给定括号字符串，我们必须做两种操作：

1. flip- 将第 i 个括号更改为相反的括号（left->right , right->left）
2. 检查字符串是否为平衡括号表达式

字符串的长度最大为 30000。

要执行的操作数最多为 100000。

应该使用什么样的数据结构来解决这类问题？

Segment Tree 是一种合适的数据结构吗？

如果是，应该如何使用它？

例子

字符串 = ()((

操作次数=4

1. 翻转 4 {新字符串是 ()()}
2. 检查{字符串是否平衡}
3. 翻转 2{新字符串变为 ((()}
4. 检查{字符串不平衡}

我有一个问题，这里显示。有人可以建议解决这个问题的方法吗？我查阅了社论，它说我们应该为每个范围创建一个树并将其视为一个节点。我无法理解这个概念和树转换的过程。提前感谢您的帮助！问题的详细信息：

如果一个序列具有以下形式，则称为正确的括号序列：

• 空序列被认为是正确的括号序列。

• (A) 被认为是正确的括号序列。

• 如果 X 和 Y 都是正确的括号序列，则 XY 被认为是正确的括号序列。

一个序列只有在形式 (A) 上才称为强括号序列，其中 A 是正确的括号序列。

您必须计算一个奇怪的和：每两个 A 子数组取 [i1, j1] 和 [i2, j2]。子数组不能相交（即 i1 ≤ i2 和 j1 ≤ i2）并且必须是强括号序列。然后，我们将子数组的最小长度加到总和上，例如它也是一个强括号序列，它同时包含 [i1, j1] 和 [i2, j2]（即如果最小长度的子序列是 [i3, j3]，则 [i3, j3] 是一个强括号序列，并且 i3 ≤ i1 ≤ j1 ≤ j3 和 i3 ≤ i2 ≤ j2 ≤ j3)。

PS我无法理解范围树转换的概念以及LCA如何在这种情况下提供帮助。谢谢。

Given an array A[] we need to find a range which has the maximum size and its minimum element is >= 1. We also need to update this range by decreasing all its elements by 1.

One idea I got is to keep a segment tree for efficient updates. But how do I get the range in <= logarithmic time?

Maybe we can use binary search here.

Thanks

我想在 n 个查询的字符串中找到一个字符的出现：例如，字符串是：“i_love_mathematics”，任务是找到：

“我”在范围内：

'_' 在范围内：

输出将是：

类似的问题是查找字符串中字符的出现次数，但复杂度为 O(N) 但在这种情况下，如果我这样做会导致非常高的复杂度，是否有一种数据结构可以可以用来解决这个问题吗？

我想知道在 Firebase 数据库中搜索并尝试了解这是否是一个好的方法或如何更改它。下面"andromeda-planetgroup.123-local1001-1234548"是一个不可变的 id 字符串，我想在包含它们的列表上执行搜索。我认为一个问题是，如果这个列表"PROPERTY"有数百个 miljons 条目并执行范围查询。

如果我创建这样的范围查询：

如果列表中有数百万个条目，我在速度方面可以期待什么。我知道如果范围查询返回 miljons if 条目，由于数据大小，它会很慢，但是可以说我想在这个范围查询中返回 10 个条目？

如果这是一个坏主意，我怎样才能让这只飞得更好？

我正在尝试获取通过 elasticsearch 索引的文档的以下部分：

我在 CURL 上使用的查询，因为我目前只是在 localhost 上测试查询，如下所示：

映射

但是上面提到的查询不会返回任何成功的命中，尽管它应该至少返回上面提到的文档。

我正在使用一个巨大的二维数据集，需要对每个点进行范围查询，将范围内的邻居作为一个集合返回我已经使用带有 KD Tree form sk learn 的索引进行了测试，但问题是，它返回的索引为一个列表和转换为一个集合需要太长时间。是否有一种数据结构，它将范围查询中的点作为集合而不是列表返回？

如果弹性搜索使用倒排索引，我想知道弹性搜索如何支持范围查询和短语查询。注意：我看到倒排索引支持它们，但我不清楚它们是如何在内部进行的。

我正在使用 Umbraco v.7.6.1 和 Examine v0.1.82 (Lucene 2.9.4.1)。我有一个车辆列表和一个搜索表单来查询不同类型的字段，包括价格。Price 字段是一个数字数据字段，在 ExamineIndex 中定义为：

问题是在搜索价格范围时，我没有结果。使用 Umbraco 后台的检查管理工具进行以下查询：

即使我有该价格范围内的车辆，也不返回任何结果。

如果我更改检查索引并从价格字段中删除 Type="INT" 标记，则范围查询将作为普通字符串范围查询工作并返回结果。

该查询对所有字符串字段都正常工作。

根据我在文档中阅读的所有内容以及之前关于考试的问题/答案，这应该适用于我正在使用的考试版本。有什么问题？

我将数据存储在弹性搜索数据库中，并尝试查询它，按数字范围过滤。

这是我数据库中文档的最小化结构：

现在我希望我的查询返回所有文档，其中“b”的任何子字段中至少有一个介于 2 和 4 之间的数字。重要的是，我不知道“”的所有子字段的名称乙”。

我提出的查询是：

查询不会出现错误，但也不会返回任何结果。我什至不确定，哪种搜索查询最适合此类任务。我只使用了查询字符串，因为它是我发现的唯一可以加入未知字段名称和范围的字符串。