3

假设我有一个包含 4 个不同值的数字的列表。我有第二个列表，描述了所有数字的总和（如果 list1=[1,3,2,5]，list2=[1,4,6,11]）。这样对于数十万个数字的列表，我不必添加所有数字 - 信息已经存储。

如果我在 list1 中的索引 0 处插入一个新数字，比如数字 2，我必须更新 list2 中的所有以下值。对于非常大的列表，这会非常耗时（也违背了第二个列表的目的）。

但是，如果我记录列表前半部分的总和 (4)，我可以从相对于该总和 (list2=[1,4,2,7]) 继续 list2。现在，如果我在 index=0 处插入数字 2，我只需要更新前两个值和记录的中间值。对于 100,000 个数字的列表，这将保证我只需要更新 50,000 个值。

我还可以在列表的每三分之一或每 10,000 个数字处记录值，或者我可以记录中途的一半（有点像二进制排序 - 现在我只需要更新/查看我正在影响的任何子列表）。

问题：我如何确定/管理此列表的最有效方法是什么？一半？三分之二？三个级别，每个级别减半？

[这是一个实际问题，而不是理论问题。List2 提供了用于布局和渲染文本/图形的偏移量。在我正在使用的环境中，一棵树是不实用的。我必须处理一个列表。我需要快速访问任何给定的总和/偏移量。另外，我很难清楚地呈现它。请随时澄清问题或要求澄清。]

4

2 回答 2

1

一种不使用树的简单方法是将主数组分解为每个 sqrt(N) 元素的 sqrt(N) 区域。对于每个部分，跟踪它所涵盖的范围以及该范围内元素的总和。现在，如果您想找到元素 k 的总和，您可以将元素 k 之前的所有 sqrt(N) 大小范围的总和相加，然后将元素 k 范围内的元素相加。这两件事都需要 O(sqrt(N)) 时间，总共需要 O(sqrt(N))。

所有操作，插入、删除和查询，都将是 O(sqrt(N))，因为在每种情况下，您都需要查询/修改 O(sqrt(N)) 列表和 O(sqrt(N)) 中的元素你的主阵列。

您还需要偶尔改革结构。何时执行此操作取决于您，但您必须定期执行此操作，否则您不会在这些操作上保持 O(sqrt(N)) 运行时。如果您在每次 sqrt(N) 修改（仅插入或删除）后完全重新制作列表，那就足够了。这将需要每个 O(sqrt(N)) 操作的 O(N) 工作，随着时间的推移，这将是每个操作的额外 O(sqrt(N)) 工作。

于 2012-08-06T03:32:36.297 回答
0

我会使用一个数组（C++ 中的向量），称之为 IndexSum，它只包含总和（您可以通过从总和中减去前一个总和来推断元素的值）。数组可以很容易地被索引并且对于顺序访问表现良好。由于数组不保留指向下一个元素的指针，因此它们很紧凑并且非常适合处理器数据缓存。我将在排序数组（向量）中保留插入和删除，称为 InsertDeleteAdjust，您可以使用二进制搜索轻松访问它...这使您可以跟踪您需要对 IndexSum 中的总和进行的调整以获取索引范围。您可以定期运行“垃圾收集”例程，使用 InsertDeleteAdjust 中的值同步更新 IndexSum。如果这种周期性“垃圾收集”的延迟

于 2012-08-06T03:13:45.173 回答