2

如果我们在长度为 n 的数组上获得一组范围S={ (x1,y1) , (x2,y2) ,......(xk,yk) }，那么我会收到来自 set 的查询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：我不想要上面两点的解决方案，我想自己想出解决方案。

4

1 回答 1

1

好的，这就去。因为我不能只给出是/否的答案。我将稍微详细说明，但不会破坏您的神秘面纱。

在 O(n) 中进行预计算，然后在 O(1) 中查询

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

在 O(nlogn) 中进行预计算，然后在 O(logn) 中进行查询

这似乎绝对是可能的。您甚至可能不需要O(nlogn)预先计算，因为您说它们已经排序。注册。查询时间，对于集合 Q 中的每个范围，都需要O(logn)时间。所以对于集合 Q 中的 k 个范围，它需要k * O(logn). 你期望你的系列 Q 有多大？

于 2013-08-08T05:59:45.347 回答