algorithm - 完全位于特定范围内的范围数

Question

假设我们有 n 个范围，每个范围由

 [l_i,r_i] where 1<=i<=n

我们有一个 [L,R] 类型的查询，其中我们必须找到完全位于给定范围内的 n 个范围中的范围数，即 [L,R]

例子：

n 范围是：

这里 n 是 2。

2 4
3 3

对于查询 3 5，输出应为 1。

对于查询 2 5，输出应为 2。

我知道 O(m*n) 的方法，其中 n 是范围数，m 是查询数，但感觉必须有更有效的实现。

Answer 1

就在这里。您想要的数据结构称为区间树。

Answer 2

对于以下解决方案，每个查询的复杂度为 O(log(n))，但它需要存储 (n^2/2) 个范围，并且预处理需要对范围进行排序（复杂度 O(n*n log(n)) 使用快速排序） ：

预处理：

1. 按 L_i 对 n 个范围进行排序

2. 对于每个范围 [L_i,R_i]：

   a) 找到 L_j >= L_i 为真的所有范围 [L_j,R_j] 的子集 S_i。

   b) 按 R_j 对 S_i 排序

查询 [L,R]：

1. 使用二进制搜索找到具有最小 L_i 的 S_i，使得 L_i >=L（复杂度 O(log(n)）。S_i 包含所有候选范围。
2. 在 S_i 中找到最大的 R_j 使得 R_j <= R 再次使用二分查找。此条目的索引对应于满足您条件的范围数。

让我们回到你的例子： S_1: [3 3] [2 4] S_2: [3 3]

1. 查询 3 5 以 S_2 结束。显然，有一个条目也满足第二个条件

2. 查询 2 5 以 S_2 结束。第二个条目是满足 R 条件的最大条目，因此结果为 2