计算落入给定范围的间隔数

Question

假设您有一个间隔列表，例如[（0 4），（1 3），（2 5），（2 6）]。此列表未排序。然后，您将得到一个范围，例如[1 5]。您必须返回适合该范围的时间间隔数。在此问题中，它将返回2。（（（1 3）和（2 5））

间隔列表保持不变，但是最多给出100000个查询，每个查询都包含一个范围。对于每个范围查询，我们都必须返回适合其中的间隔数。

研究后，我读到了Interval Trees。但是，您只能查询具有任何给定范围的overlap间隔，而我正在寻找<< fallover范围的间隔。这些查询需要对数时间。

有没有办法在类似的时间复杂度下解决此问题，可能会改变间隔树？我不是在寻找线性解决方案（因为蛮力总是意味着扫描所有间隔）。

Answer 1

[假设如果您要添加一个间隔，该段不会那么长，那么您可以记住树节点中的id，并且您只需记住穿过点[[a和

b的段，因此，您只需要让段树获取id穿过a和b的向量即可。然后从另一棵树中询问段a-b中的结尾数。之后，您只需删除一次发生的ID。它应该更快。