有效地找到 item.x > n 和 item.y < n 的数组项

Question

（示例是 Javascript，但答案可能与语言无关）。

我有一个包含 from 和 to 字段的对象列表：

const items = [
   { id: 1, from: 4, to: 10 },
   { id: 2, from: 1, to: 6  },
   { id: 2, from: 11, to: 20  },
];

我想过滤给定数字 x 的列表，以便我得到 from < x 和 to > x 的元素。所以：

fn(5, items) === [ 
   { id: 1, from: 4, to: 10 },
   { id: 2, from: 1, to: 6  },
];

当然我可以在 O(n) 中使用 Array.filter:

function fn(x, list) {
   return list.filter(element => ( element.from < x) && (element.to > x));
}

但是 O(n) 对我来说是个坏消息，因为数组可能很长，我需要经常重复查询。

我怎样才能更有效地做到这一点？我不介意索引/排序的前期开销。

我想出的最好办法是制作两个排序列表，一个按 from，另一个按 to。二进制搜索都创建一个元素列表 from < x 和另一个元素列表 from > x，然后得到这些列表的交集。但是这些列表也可能很长，所以交集部分会很慢。

Answer 1

您可以使用具有不同性能特征的多种数据结构。您可以使用四叉树、k-d 树等。一般来说，它们类似于 O(k log(n) log(n))，其中 k 是结果集中的点数，n 是数据结构中的点数。

所有这些背后的想法是，您将 space 水平和垂直划分，直到大小为 1。这使得它们 O(log(n)) 到 insert/delete .但是然后你的范围搜索你遍历这些框，直到你得到一个框，它要么一直在你的范围内，一直在你的范围内，要么包含一个元素（你看到的）。

Answer 2

似乎这种查询的规范数据结构是区间树。

这是一个二叉树，每个节点存储：

要查询，走树：

它也可用于查找与另一个区间的重叠，而不仅仅是一个点。

线段树这一相关结构适用于更多类型的查询。

Efficiently find array items where item.x > n and item.y < n