问题标签 [interval-tree]

我有一组房间和通道，我可以将它们转换为矩形（x，y，宽度，高度）或点列表（x，y）。Room并且Passage都扩展了Pointable接口。getPoints() 方法为 Room 类实现为

问题：
我必须确定Pointable一个给定的Point所属。没有房间相交。我最初使用 aHashMap<Point,Pointable>将每个Point与 a相关联Pointable，它能够在 O(n) 时间内快速访问答案。但是，现在需要HashMap在生成关卡时重新计算多次。

此时，使用 HashMap（考虑到生成和访问）是否仍然更有效，还是应该使用另一种方法，例如一组 2-D 区间树？

【挑战结束】

问题：

一组正元素。Deepu 想减少数组的元素。他调用了一个函数 Hit(X)，它将数组中大于 X 的所有元素减少 1。

他会多次调用这个数组。在多次调用 Hit(X) 后打印数组。

输入：

n----- 数组 10^5 中没有元素。

n 个元素 ----- 1<=元素<=10^9。

x----- 对 Hit(X) x 个元素的调用次数----- 1<=element<=10^9。

输出：

打印调用 Hit(X) x 次后的数组。

时间限制--5 秒。

我的解决方案给出了 Time Limit Exceeded。

我的做法：

1. 保留原始数组
2. 创建数组元素对的向量及其在数组中的索引 对向量元素进行排序 [ 升序 ]。
3. 执行 C++ STL 的 LowerBound() 以获取元素在向量中的位置，其中元素等于给定元素 x。
4. 从这个元素开始，将大于 x 的元素减少 1，直到从对中的索引开始在原始数组中结束。
5. 对每个 x 重复步骤 3 和 4。
6. 打印原始数组。

我认为我的解决方案复杂度为 n^2。

谁能给我一个优化的解决方案

谢谢

我的代码

我正在寻找一种数据结构，它可以在具有以下属性的封闭区间内有效运行：

• 动态添加或删除间隔

• 为每个间隔设置并随时更改一个数字（“深度”）。没有两个深度是相同的

• 查找与任何给定间隔重叠的所有间隔，按“深度”排序

我找到的最接近的结构是区间树，但它以任意顺序列出了找到的区间，相对于它们的深度。我可以收集报告的所有“未排序”间隔，然后对它们进行排序，但我希望可以避免对每个查询的结果进行排序。

请问，有没有人知道这种数据结构或有任何建议（如果可能的话）来增强间隔树以支持这种排序？

例子：

1. 将 [1,2] 添加到空结构并将其深度设置为 1
2. 添加 [10,100]，深度 = 2
3. 添加 [5,55]，深度 = 3
4. 查询 [5,50] 报告 [10,100] 和 [5,55]
5. 将 [10,100] 的深度设置为 3，将 [5,55] 的深度设置为 2
6. 查询 [5,50] 报告 [5,55] 和 [10,100]

编辑

我对快速添加/删除和查询更感兴趣，而不是更新深度。如果这有助于加速其他操作，则深度可能需要 O(n)。

我在谷歌上搜索了一下这个主题，并在http://www.geeksforgeeks.org/上找到了这个

区间树主要是一种几何数据结构，通常用于窗口查询，例如，在矩形视口内查找计算机化地图上的所有道路，或查找三维场景内的所有可见元素。

现在我的问题实际上分为两部分：

• 如何使用区间树在计算机地图上查找所有道路？
• 区间树的实际应用还有哪些其他示例？

PS：欢迎参考更多关于区间树的阅读材料进行简要说明

我正在用 C# 编写一个区间树。我想做的只是扩展现有的二叉搜索树来存储间隔，而不必重写核心功能（添加、获取、删除）。

在 BST 内部，我有一Node堂课：

在区间树内，我有一个IntervalNode扩展类Node：

我遇到的问题是试图存储IntervalNode在树中而不是Node. 我现在有什么方法可以使用现有的基础实现AddwithIntervalNode吗？

我想我想做的是这样的：

给定一个大小为 n 的数组，对于从 1 到 n 的每个 k，找到大小为 k 的连续子数组的最大和。

这个问题有一个明显的解决方案，时间复杂度 O(N ² ) 和 O(1) 空间。卢阿代码：

有没有时间复杂度较低的算法？例如，O(N log N) + 额外的内存。

相关话题：

• Kadane 算法

对于分段树的惰性传播算法，我有一些不清楚的地方。根据下面的代码，当查询间隔完全重叠时，更新值只是添加到父节点，子节点被标记为延迟更新。但正如您在所附图片中看到的那样，如果对范围 0,1 进行了 +4 更新，那么两棵树的结果完全不同！（左图：没有延迟传播）。

所以问题是，如果在 +4 更新后调用了一个询问 0,1 和的查询怎么办？

我想知道是否有人实现/知道将处理循环间隔的（最好是javascript）间隔树算法。通过循环，我的意思是开始>结束的间隔。请注意，这也需要限制间隔的大小。

这只是常见区间树问题的一个子案例吗？

回答评论中提出的问题：这是我所说的圆形子范围的图像（感谢 G. Bach 和维基百科）：

并且（与上图无关）这是范围的示例 json 表示：[{id: 'range1', start: 3, end: 34}, {id: 'range2circular', start: 30, end:6}]

希望

谢谢！

我正在查看区间树文章中的增强树，并查看 SWI-Prolog 标准库中的rbtrees.pl。文章说：

然后将一个额外的注释添加到每个节点，记录从该节点向下的所有间隔中的最大上限值。维护此属性涉及在添加或删除节点时从下到上更新节点的所有祖先。

我很容易看到如何添加此注释。假设我想存储区间7-45。我使用 7 作为键，为了我的价值，我使用了一个包含我所有信息的结构，所以类似于interval(7-45, MaxBelow). 但我不清楚我将如何“更新节点的所有祖先”，因为在rb_insert/4. 我没有看到一种方法来获取在前后树之间发生变化的所有节点的列表（无论如何生成这样的列表可能会很奇怪且效率低下）。

有没有办法用这种方法来构建这个结构rbtrees.pl？

顺便说一句，rb_empty使用未实例化的变量作为空节点对我来说很有趣。是否有一个原因？

编辑：在我看来，我可以检查前后树并尝试统一之前和之后的分支以找到它改变的路径。这会颠覆我追求的性能提升吗？

问题是：

• 给定长度为 n 的字符串和 m 个查询。

• 每个查询都是以下两种情况之一：

  • 相反地​​改变第i个字符
  • 检查从第 u 个字符到第 v 个字符的子字符串是否是正确的括号表达式。如果是，则打印 1，否则打印 0。

时间限制：0.2s

在这些情况下，定义了正确的括号表达式：

• 长度为 0 的字符串

• 一个字符串只包含 '(' 和 ')'

• 如果 A 是正确的括号表达式，则 (A) 也是正确的括号表达式

• 如果 A 和 B 是正确的括号表达式，则 AB 也是正确的括号表达式

我的主要想法类似于 CodeForces 上的问题380C，http: //codeforces.com/blog/entry/10363

然后我检查给定范围内的最长子序列是否等于范围的长度，所以我会得到答案。但是我遇到了时间限制错误。

我整天在互联网上搜索这个，但我没有得到答案。如果你能帮助我，我将不胜感激。:)

这是我的代码：https ://github.com/hoangvanthien/GH_CppFiles/blob/master/SPOJ/NKBRACKE.cpp