algorithm - 查找 pt 所在的线段数

Question

给定 n 个线段和一个 pt。我想找到 pt 所在的线段。线段由 x[start] 和 x[ending] 表示。可以假设所有线段都在 x 轴上。线段也可能重叠。有没有比 O(n) 更好的解决方案。我认为如果这些段不会重叠排序并且二进制搜索会成功。有很多点，我想找到每个线段上的点数

Answer 1

再好不过了O(n)。您必须检查每个部分。排序更糟糕 - O(N log N)。

Answer 2

我相信你问这个是因为你想查询多个 pt。

考虑到所有段都包含 pt，如果您想准确找出哪些段n包含 pt，那就再好不过了。O(n)

但是，如果您只想计算数量，您可以使用一些数据结构来优化您的查询。likebinary indexed tree可以让你为一个查询O(nlog)做准备。O(log)

Answer 3

如果我正确理解了这个问题，可以通过“所有线段都可以假定在 x 轴上”。您的意思是说您有一组（重叠）间隔并用点查询它们，对吗？

如果是这样，我会提出以下方法：

1. 将输入区间转换为具有权重的一组新的非重叠区间，其中区间的权重是该区间所在的原始区间数。例如，如果您有输入{(0, 2), (1, 3)}，则将其转换为{(0, 1)=>1, (1, 2)=>2, (1, 3)=>1}。不久前我写了另一个关于如何处理重叠间隔的答案。你的问题不同，但方法是一样的。
2. 在这些新间隔上构建一个段树来执行查询。

给定n间隔，您可以及时执行第一步O(n log n)。您最终会得到O(n)新的间隔，因此构建段树O(n log n)也需要时间。然后可以及时进行查询O(log n)。