algorithm - 查询的复杂性？

Question

如果给定一组范围 S={ (x1,y1) , (x2,y2) ,......(xk,yk) } 一个长度数组n.然后我得到来自集合Q={ (l1,r1) , ......(li,yi) } 的查询。每个查询 (li,ri) 表示集合 S 中有多少个范围落在这个范围 (li,ri) 之间。
我只想知道以下事情是否可行:

  1. Pre-computation in O(n) and then queries in O(1)
  2  Pre-computation in O(nlogn) and then queries in O(logn)

PS:我不想要以上两点的解决方案，我想自己想出解决方案。

Answer 1

好的，开始吧。因为我不能只给出是/否的答案。在不剧透你的神秘感的情况下，我会稍微详细说明一下。

Pre-computation in O(n) and then queries in O(1)

既然你提到集合 S 中的范围是排序的(比如在结束元素上)。我们可以在没有任何预先计算的情况下继续进行。有了这个，我相信我们可以在分治策略的帮助下实现 O(logn) 的查询时间。但是获取O(1)的查询时间似乎有点牵强。即使使用 range trees或 kd-trees ，您可以期望的最好的是 O(log) 复杂性。也许如果我们使用一些辅助数据结构(比如哈希表)和给定的集合，我们可以尝试做一些事情，但 O(1) 似乎有点雄心勃勃。所有这些都值得一问，您的空间要求是什么？

Pre-computation in O(nlogn) and then queries in O(logn)

这看起来绝对有可能。您甚至可能不需要 O(nlogn) 进行预计算，因为您说它们已经排序。注册。查询时间，对于集合 Q 中的每个范围，它需要 O(logn) 时间。因此对于集合 Q 中的 k 个范围，它需要 k * O(logn)。你希望你的 Q 值有多大？