查找给定范围内的对值

Question

我有一个数组或N对(v1, v2)，其中v1 <= v2。这些应该代表时间从开始到v1结束的事件v2。它们可以相等，那么事件是瞬时的。该数组按开始时间排序v1。

对于给定的范围(L, R)，我想找到任何一对L <= v1 <= R or L <= v2 <= R。这里的想法是让事件在给定范围内开始，发生或结束。

我的主要问题是效率。该数组可能包含数十万个事件。因此，仅线性搜索遍历所有对是不可行的。

我读了一些有关kd-tree的文章，但是它的问题是它排除了范围的边界，只会返回L <= v1 <= R AND L <= v2 <= R。也就是说，只会返回范围内实际发生的事件（开始和结束），而我需要开始或结束（或显然是两者）。

我还考虑过保留2个查询表（我花了两倍时间）

std::map<double, Event*> startPoints;
std::map<double, Event*> endPoints;

并std::find在两者中使用算法并合并结果。

只是寻找建议，这是一个好的解决方案，还是有更聪明的方法。

编辑：

重新考虑这一点，它更加复杂。这是预期结果的一个例子

• L <R：范围足够大

|---Ev1---|     |---Ev3---|     |---Ev5---|
        |---Ev2---|     |---Ev4---|
             |               |
             L               R

在这里，我想获取Ev2（在范围内结束），Ev3（在范围内发生）和Ev4（在范围内开始）

• L <R：范围太小，无法完成一个完整的事件

|---Ev1---|     |---Ev3---|     |---Ev5---|
        |---Ev2---|     |---Ev4---|
                    |    |
                    L    R

在这里，我想得到Ev3，因为它当前正在范围内运行，而Ev4是它在范围内开始运行

• L == R：如果我想知道某一时间点会发生什么

|---Ev1---|     |---Ev3---|     |---Ev5---|
        |---Ev2---|     |---Ev4---|
             |
             LR

在这里，我只需要Ev2，因为它是当前运行的唯一Ev2。

Answer 1

由于您需要处理三种情况——在给定范围内开始、发生或结束，我们可以将其分为三个部分。

1. 起始：v1位于[L,R].
2. 结局：v2在于[L,R].

第三种情况可以表示为v1 <= R and L <= v2，但前两种情况部分覆盖了这种情况，因此我们将使用不同的公式来避免冲突：

3. 发生：v1 < L and R < v2

好吧，如果我们可以按 来对事件数组进行排序，那么以对数加报告事件数的时间来处理第一种情况就很容易了v1。同样的技巧适用于第二种情况。

第三种情况比较棘手。我们来画一下：

粉色区域代表所有音程L <= R。红点是一个区间，绿色区域代表我们想要捕获的所有可能的事件。要进行这样的捕获，可以使用k2-tree。