一系列交集算法比O（n）的更好吗？ [英] A range intersection algorithm better than O(n)?
问题描述
范围交集是一个简单的，但不平凡的问题。
Range intersection is a simple, but non-trivial problem.
它已经回答了已经两次：
Its has been answered twice already:
- <一个href="http://stackoverflow.com/questions/224878/find-number-range-intersection">http://stackoverflow.com/questions/224878/find-number-range-intersection
- <一个href="http://stackoverflow.com/questions/143552/comparing-date-ranges">http://stackoverflow.com/questions/143552/comparing-date-ranges
- http://stackoverflow.com/questions/224878/find-number-range-intersection
- http://stackoverflow.com/questions/143552/comparing-date-ranges
第一解决方案是O（n）和第二溶液为数据库（小于当然为O（n））。
The first solutions is O(n) and the second solution is for a database (which is less than O(n) of course).
我有同样的问题，但对于大的n，我不是一个数据库中。
I have the same problem, but for a large n and I am not within a database.
此问题似乎是非常相似的<一href="http://stackoverflow.com/questions/303243/store-2d-points-for-quick-retrieval-of-those-inside-a-rectangle">http://stackoverflow.com/questions/303243/store-2d-points-for-quick-retrieval-of-those-inside-a-rectangle但我不明白它是如何映射。
This problem seems to be very similar to http://stackoverflow.com/questions/303243/store-2d-points-for-quick-retrieval-of-those-inside-a-rectangle but I don't see how it maps.
那么，什么数据结构将您存储集范围，使得在一个范围搜寻成本小于O（N）？ （附加题使用可用的库用于Java）
So what data structure would you store the set of ranges in, such that a search on a range costs less than O(n)? (Extra credit for using libraries available for Java)
编辑：
我想获得的所有交叉范围的子集，这意味着搜索范围可以交叉多个范围。
I want to get a subset of all intersecting ranges, meaning the search range could intersect multiple ranges.
这需要比为O（n）在Java中要少的方法是：
The method that needs to be less than O(n) in Java is:
public class RangeSet {
....
public Set<Range> intersects(Range range);
....
}
在哪里范围仅仅包含一对INT开始和结束的一类。
Where Range is just a class containing a pair of int start and end.
这是不是一个不可能的问题，我已经有解决方案，我只是想看看是否有这样做的更标准/更简单的方法
This is not an impossible question, I already have the solution, I just wanted to see if there was a more standard/simpler way of doing it
推荐答案
标准的方法是使用的间隔树。
在计算机科学中，一个区间树是一种树形数据结构来保存的时间间隔。具体而言，它允许人们有效地找到与任何给定的时间间隔或点重叠所有间隔。它通常用于窗口查询，例如，寻找在电脑地图上的所有道路矩形视口内，还是找一个三维场景内的所有可见的元素。类似的数据结构是段树。
In computer science, an interval tree is a tree data structure to hold intervals. Specifically, it allows one to efficiently find all intervals that overlap with any given interval or point. It is often used for windowing queries, for instance, to find all roads on a computerized map inside a rectangular viewport, or to find all visible elements inside a three-dimensional scene. A similar data structure is the segment tree.
的平凡解是访问每个间隔并测试它是否交叉的给定的点或区间，这需要O（n）的时间，其中n是时间间隔集合中的数目。因为一个查询可能返回所有间隔，例如，如果该查询是一个大的间隔相交的集合中的所有的间隔，这是渐近最优;然而，我们可以做到通过考虑输出敏感的算法，其中所述运行时是pssed中的米，该查询生成区间的数目而言前$ P $更好。区间树有邻查询时（登录N + M）和邻初始创建时间（n log n）的，同时限制内存消耗为O（n）。创建后，间隔树可能是动态的，允许区间为O高效插入和删除（log n）的。如果间隔的终点是一个小整数范围内（例如，在范围[1，...，O（N）]），更快的数据结构存在[1] preprocessing时间为O（n）和查询时间O（1 + M）报告米的间隔包含一个给定的查询点。
The trivial solution is to visit each interval and test whether it intersects the given point or interval, which requires O(n) time, where n is the number of intervals in the collection. Since a query may return all intervals, for example if the query is a large interval intersecting all intervals in the collection, this is asymptotically optimal; however, we can do better by considering output-sensitive algorithms, where the runtime is expressed in terms of m, the number of intervals produced by the query. Interval trees have a query time of O(log n + m) and an initial creation time of O(n log n), while limiting memory consumption to O(n). After creation, interval trees may be dynamic, allowing efficient insertion and deletion of an interval in O(log n). If the endpoints of intervals are within a small integer range (e.g., in the range [1,...,O(n)]), faster data structures exist[1] with preprocessing time O(n) and query time O(1+m) for reporting m intervals containing a given query point.
这篇关于一系列交集算法比O（n）的更好吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
