问题标签 [range-query]

在最近的一次采访中，我被问到这个问题：给定一个 BST，其节点包含一个整数作为值，找到其节点位于整数 X (min) 和 Y (max) 之间的所有子树，其中 X<Y。这些子树不能相互重叠。

我已经解决了这个问题的变体，例如 - 打印在给定范围内的 BST 键。但是无法弄清楚这一点，因为它涉及找到满足非常特定约束的主图/树的所有连接子图。任何指针/帮助/伪代码表示赞赏。

添加注释 -

1. 该问题将节点的数据结构定义为具有左指针、右指针和整数值。没有办法标记节点。
2. 被要求用Java解决这个问题。
3. 当我说子树/子图时，我指的是一组连接的节点，而不是不相交节点的列表。对困惑感到抱歉。

我有以下代码，用于具有延迟传播的分段树，我可以设法编写。此代码不适用于将某个范围内的所有数字与一个值相乘，例如 x。我认为我在 update_mult 函数中做错了什么。树维护范围的总和。

我无法弄清楚 update_mult 的问题。专家，你能帮我找出我在实施中哪里出了问题吗？

所以我再次需要一些帮助。我最近开始在 codechef 上做中级问题，因此我得到了很多 TLE。

所以基本上问题是找到问题中给出的多个最大范围查询的总和。给出初始范围，然后通过问题中给出的公式计算下一个值。

我使用段树来解决问题，但我一直在为一些子任务获取 TLE。请帮我优化这段代码。

问题链接 - https://www.codechef.com/problems/FRMQ

我想开发一个范围搜索算法，报告查询点给定距离内的所有点。

这些点由 d 个整数坐标在一个很小的范围内指定，例如每个维度最多 6 位（范围 0..63），总位数不超过 60 位。

距离度量是曼哈顿或欧几里得（由您决定），即绝对或平方坐标差的总和。在每个维度一个比特的特殊情况下，它相当于汉明距离。

最多可以有一百万个点。

您是否知道在这种情况下支持快速查询O(Log²(n)+k)或类似（带有空格O(n)）的实用数据结构？还需要合理的预处理时间（二次）。

k-D树是第一选择，但恐怕它们没有利用坐标的有限性，并且可能在高维度上表现不佳。

每个坐标只有一位的情况特别有趣。即使是部分解决方案也是受欢迎的。

给定墙的水平截面，以及从坐标 Xi 到 Yi 应用的 N 层油漆，输出可见的不同层数。

这是问题链接http://www.spoj.com/problems/POSTERS/

这是我的解决方案http://ideone.com/gBJKnL

方法：我尝试通过 Segment Tree 懒惰地更新子节点值来解决问题，最近的值在他们的懒惰更新中替换了旧的值。这样，只有最近的油漆被应用到水平横截面。尽管代码在自定义测试用例上运行良好，但它会占用大量内存并被在线法官中止。

我正在写一份医生计划的申请。医生是具有 ID、名称和计划集合的 Java 对象。计划由 {start_date, end_date, planning_type} 描述。日期格式为 YYYY-MM-DD。现在，考虑具有两个计划范围的医生 A：（单击“运行代码片段”代码以将计划视为 HTML 表）

例如，如果我们尝试检查该医生是否在 2016-01-07 工作，则查询应如下所示：

此查询将在结果集中返回医生 A，尽管这不是真的。实际上医生 A 不会在工作，但是，由于 Lucene 存储集合的方式，此查询匹配医生 A。

有没有办法（包括添加额外的字段，......）让它按预期工作？

嗨，我想索引看起来像这样的对象

有没有办法编写一个查询来匹配包含 uuid: "345" 和 uuid: "789" 但第二个的顺序最多比第一个大两个的子句的所有对象？

所以上面的例子会匹配，但下一个不会：

原因是“789”子句的顺序是 4，比“345”子句的顺序为 1 大 2 个以上。

任何帮助表示赞赏！谢谢，迈克尔

我正在使用python 弹性搜索客户端来查询我的弹性搜索索引。我的索引非常小，因为我试图推断出我的查询出错的地方。这是一个示例条目

和另一个

和另一个

基本上，今年每个月的所有 15 号。

这是我的查询/请求

当我在异常中不可避免地碰到断点时，异常如下。

关于“查询不支持 [格式]”的某些内容似乎是一个常见的字符串。

我认为这可能是我最初映射索引的方式的问题，所以我删除并重新映射如下。

仍然没有运气。我正在尽力按照本指南进行范围查询。我不知道我做错了什么。请帮忙。

更新：我从查询中删除了“格式”，现在它看起来像这样。

我得到了想要的条目。但是为什么我不能使用“格式”作为参数呢？

我将如何构造一个 ElasticSearch 查询来满足以下要求：

价格必须在 100,000 到 200,000 之间，但也显示超出此范围的结果，但如果高于 200,000 或低于 100,000，相关性会降低。

到目前为止，我有以下内容，但它似乎没有做我想做的事情（为简洁起见，省略了包装查询）：

更新：

再看一眼，我认为将函数设置为以下，没有范围查询就可以了，不是吗？

非常感谢！李

我正在准备面试，并试图了解这个问题：

编写一个程序来跟踪一组文本范围。起点和终点将是字符串。

文本范围示例：[AbA-Ef]

• Aa 将落在此范围之前
• AB 会在这个范围内
• 等等

有人可以帮我理解文本范围[AbA-Ef]是如何定义的吗？

• 是AbA起点还是Ef终点？

• 我可以从概念上理解 char 的起点A，但我没有得到起点AbA。它像数字线，其中 char A, a, B, b, C,c落在线上吗？

• 就像正则表达式，起点AbA暗示所有以前缀开头的字符串AbA？

• 是[AbA]吗[Ef]？

• 或{Ab}+ [A-E]+ {f}？

提前致谢。