1

我有一个大（> 百万个元素）树，每个元素都有一个“偏移”字段，它引用外部的东西。我需要做这两个：

  1. 在任意位置插入新元素。每次插入都会导致后面元素的“偏移”字段增加一些量。
  2. 快速获取元素的偏移值。

如果 2 不是必需的，我会存储相对于前一个的偏移量，那么插入后就不需要更新所有内容。但这意味着我需要将每个先前的偏移量相加来计算一个元素的绝对值。

有没有做这种事情的规范方法？我在想也许是一种折衷方案，例如，每个第 n 个元素都有一个绝对偏移量，而其他元素的偏移量将相对于前一个绝对偏移量，这意味着在这两种情况下我都必须进行少量遍历。

4

1 回答 1

1

有一些方法在某种程度上基于您让某些元素存储绝对偏移量的想法。

其中一个（我认为它是分层向量的一个版本）是存储第一个连续sqrt(N)元素的偏移量变化，然后存储元素 from sqrt(N)to2 * sqrt(N)等等。然后，为了找到给定元素的偏移量，您需要将先前元素的所有连续总和（最多为sqrt(N) + 1, since (sqrt(N) ^ 2) = N）相加，然后添加最后一个整组之后但在您的元素之前的元素'感兴趣。这为您提供了O(sqrt(N))插入和查找时间。

您还可以将此方法提升到一个新的水平，并将总和存储为：

  • 整个区间
  • 区间的前半段和后半段
  • 第一...第四季度等

这样，您将获得一个类似于区间或段树的数据结构，但不完全相同。它可以使用简单的数组实现为完整的二叉树。它为您提供O(log N)了两种操作的复杂性。

对这个想法的一些改进导致了二叉索引树，它具有相同的复杂性，但使用了大约一半的空间。

于 2012-10-17T10:45:51.487 回答