你被给定了一个区间集合S。你需要在最短的时间复杂度内找出所有被给定区间(a, b)包含的S中的区间。

Question

你将会获得一个区间集合 S。你需要在最小时间复杂度内找到所有被给定区间 (a, b) 包含的区间 S 。通过暴力可以用 O(n) 的时间完成，其中 n 是集合 S 中的区间数。但是，如果我允许做一些预处理，能否在 less than O(n) 的时间内完成，例如 O(log n) 时间？

起初我想到 interval tree，但我认为它在这里不适用，因为区间树用于获取与给定区间重叠的所有区间。

- Steve M

---

如所述，最好的情况是O(n)，因为在最坏的情况下，必须将S的所有元素都复制到输出中。 - Patricia Shanahan

是的，那是正确的。但我希望得到类似于O(logn) + O(m)这样的东西，其中m是输出中元素的数量。 - Steve M

请注意，就大O符号而言，O(logn)+O(m) = O(n)，因为m可能与n一样大。预处理时间也包括在运行时间内，因为如果您想要对区间进行排序或使用某些数据结构进行排列，则这些都是算法的一部分。 - Fallen

相关链接：https://cs.stackexchange.com/q/77008/55291 - plasmacel

Answer 1

您可以在二维平面中重新设计您的问题。让每个区间的（begin，end）成为一个二维点。（请注意，所有有效的区间最终都会位于对角线上方）

您的区间搜索问题转化为经过良好研究的正交二维范围查询，其算法具有或运行时间，其中k是报告的点数。

- Thomas B.

---

好点子，但我不知道是否有复杂度小于O(k)的算法，其中k是报告的点数。 因此，Patricia是对的。 - Matthias

是的，没错。我已经更新了我的答案，包括k的描述。但有时数据点分布得很好，你的查询只涵盖了一个小集合，因此摊销的k << n。 - Thomas B.

Answer 2

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

预处理：

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

搜索：

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

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

- Evgeny Kluev

---

看起来它的空间复杂度是O(n^2)。如果我错了，请纠正我。 - Steve M

@SteveM: 空间复杂度为O(n*log(n))。持久化数据结构允许创建浅层次的“拷贝”，其中大部分数据在“拷贝”之间共享，因此每个BST更新仅需要O(log(n))个附加节点。 - Evgeny Kluev