algorithm - 存储快速查询范围的最佳数据结构是什么？

Question

我有这种情况，我有 N 个时间线，每个时间线都包含 block 。这些 block 包含具有特定索引的 token ，并且知道它们的最大和最小 token 索引。还有一个索引将 block 的第一个索引映射到(时间线， block )对。这是一个例子:

Timeline 1: [1 2 5 8 9 11] [14 17 18 21] [22 23 25 26] ...
Timeline 2: [3 4 6 7 10 12] [13 15 16 19 20 24] [27 28 34 45] ...

Index:
  1 -> timeline 1, block 1
  3 -> timeline 2, block 1
  13 -> timeline 2, block 2
  14 -> timeline 1, block 2
  22 -> timeline 1, block 3
  27 -> timeline 2, block 3

如您所见，没有丢失 token (没有间隙)。

那些数据结构是我最初拥有的。 优化特定 token 索引查询的最佳替代数据结构是什么？假设我想检索 token 19。现在我要做的是:在索引中进行二分搜索以找到好的每个时间线的 block ，然后在每个 block 内进行完整搜索。对于标记 19，二分法搜索将产生 block (1, 2) 和 (2, 2)，其中可以包含 19，然后进行完整的线性搜索以找到标记 19(此处不可能在 block 内进行二分法搜索，因为标记有各种大小，尚未包含在任何数据结构中)。

谢谢!

编辑:我正在考虑使用包含所有时间线间隔的间隔树。问题是查询仍然会导致许多间隔。此外，与二进制搜索相比，它并没有优化太多。

Answer 1

您可以有一个 A 数组，其中包含 t 个指向对象的指针，这些对象包含指向 token 、其时间线和 block 的指针。如果您可以使用您的语言喜欢的任何机制将引用保存在数组中。如果您不能在 block 内进行二进制搜索，我不确定您可以做什么。