algorithm - 给定一组区间 S。您必须以最小时间复杂度找到 S 中包含在给定区间 (a, b) 中的所有区间

Question

给你一组区间S。您必须以最小的时间复杂度找到S给定间隔中包含的所有间隔。(a, b)

这可以O(n)通过蛮力及时完成，其中n是 set 中的间隔数S。但是如果我被允许做一些预处理，这可以在更短的O(n)时间内完成吗？例如O(log n)时间？

最初我在考虑区间树，但我认为它不适用于这里，因为区间树用于获取与给定区间重叠的所有区间。

Answer 1

您可以在 2D 平面中重塑您的问题。让(begin, end)每个区间的 是一个二维点。（请注意，所有有效间隔都将在对角线上结束）

您的区间搜索问题使用具有或运行时的算法转换为经过充分研究的正交 2D 范围查询，其中 k 是报告的点数。

Answer 2

这里可以使用持久二叉搜索树。

预处理：

1. 创建空的持久树。它应该存储按结束点排序的间隔。
2. 按起点对区间进行排序。
3. 对于每个间隔，从排序列表的末尾开始，创建持久树的“副本”并将此间隔添加到此副本。

搜索：

1. 在排序列表中查找查询区间的起点。
2. 从最小键到查询间隔结束迭代持久树的相应“副本”。

搜索时间复杂度为 O(log(n) + m)，其中 m 是输出中的元素数。