高效数据结构，用于计算序列平均值

Question

高效数据结构，用于计算序列平均值

algorithmdata-structures

6

我需要设计一个数据结构，能够高效地支持以下操作：对存储为我所需的数字序列执行以下操作：

将整数x添加到序列的前i个元素中
在序列末尾追加整数k
删除序列的最后一个元素
检索序列中所有元素的平均值

示例

从空序列[]开始

追加0（[0]）
追加5（[0, 5]）
追加6（[0, 5, 6]）
在序列的前2个元素中添加3（[3, 8, 6]）
检索平均值为5.66（[3, 8, 6]）
删除最后一个元素（[3, 8]）
检索平均值为5.5（[3, 8]）

之前的工作

我考虑使用Fenwick Trees(Topcoder Editorial)，但这需要指定序列的最大大小来初始化Fenwick树，而我不一定知道。但是，如果我有一个序列可以支持的最大元素数量，如果我还保存了序列中所有元素的总和，我就可以在O(lg N)上执行这些操作。 编辑：这个问题是为Codeforces problem而提出的，我需要所有操作都具有亚线性运行时间，因为将元素添加到第一个元素中，在最坏情况下可能与添加到整个序列相同。

- Gustavo Torres

1

这是干什么用的？那第一个操作很不寻常。 - Colonel Panic

我一直在尝试解决Codeforces上的一个问题，但是我只能使用树，但由于树的数组初始化（我想）导致解决方案显然太慢了。 - Gustavo Torres

6个回答

2

听起来像是使用双向链表来维护头尾引用，同时保持当前总和和计数的方式。

将整数x添加到序列的前i个元素中

从 *head 开始，添加 x ，然后移动到下一个项目。重复 i 次。 sum += i*x

将整数k附加到序列的末尾

从 *tail 开始，创建一个新项目，头部 = 尾部，尾部 = null。相应地更新 *tail、sum 和 count。

删除序列的最后一个元素

将 *tail 更新为 *tail->prev。更新 sum，减少 count

检索平均值 5.5 ([3, 8])

返回 sum / count

- Matt Dodge

虽然你可以使用单向链表来实现这个，但是不需要双向链接。只需保持头指针和尾指针即可。+1 - Jim Mischel

1

没有前一个元素的链接，删除最后一个元素就变成了O(n)，对吧？必须知道要更新*tail到什么。 - Matt Dodge

不，你需要两个 -- 你需要能够在常数时间内找到倒数第二个，并且你需要能够按比例遍历任意大小的前缀。 - jacobm

他说需要亚线性，而不是O(N)的“重复i次”。 - Rusty Rob

1

你可以使用树状数组（log(n)）来解决问题。另一个选项是一次性回答多个查询。例如，如果你有以下(i, x)对：(1,1), (2, 1), (3, 1)，那么你只需要进行三次操作，而不是进行3+2+1次操作（这只是一个不好的例子）。 - Rusty Rob

显示剩余2条评论

1

为了满足第一个要求，您可以维护一个单独的添加操作数据结构。基本上，它是一组有序的范围和增量。您还需要维护这些添加的总和。因此，如果您将5添加到前三个项目，然后将12添加到前10个项目，您将拥有：

{3, 5}
{10, 12}

这些加法的总和为(3*5) + (10*12) = 135。

当被要求提供总和时，您需要提供项目总和和这些加法的总和。

唯一的麻烦是当您删除列表中的最后一个项目时。然后，您必须浏览这些加法集合以查找包括最后一个项目（即您正在删除的项目）的任何加法。该数据结构可以是哈希映射，其中键是索引。因此，在上面的示例中，您的哈希映射将是：

key: 3  value: 5
key: 10 value: 12

每当您执行第一个操作时，都会检查哈希映射以查看是否已经有该键的项目。如果有，则只需更新那里的值而不是添加新的增量。并相应地更新总和。

有趣的是，您甚至不必保留额外的加法总和。您可以在处理过程中更新总和。

当您从列表中删除最后一个项时，检查哈希映射以查看是否有该键的项。如果有，则删除该项，减少键，然后将其添加回哈希映射（或者，如果存在，则更新具有该键的现有项）。

因此，使用由mattedgod提出的双向链表，其中包含他建议的总和。然后使用此哈希映射来维护您对列表的添加，相应地更新总和。

- Jim Mischel

1

这种数据结构可以只是一个元组（N，S）和数字的堆栈。没有花哨的东西。所有操作都是O（1），除了第一个操作是O（i）。

- Timothy Shields

1

我建议您尝试使用二进制索引树。

它们允许您在O(Log(n))中访问累积频率。

您还可以按顺序log(i)添加前i个元素。

但是，不要将前i个元素增加X，而是将第n个元素增加X。

要删除最后一个元素，也许需要另一棵树来累加已经被删除的数量。（所以不是删除，而是将那个数量添加到另一棵树上，每次访问第一棵树时从结果中减去）。

对于追加，我建议您从大小为2*N的树开始。然后，如果您的数据超过了2*N，请添加另一棵大小为2*N的树。（不确定最佳方法是什么，但希望您能够解决这个问题）。

- Rusty Rob

所以，你不是将前i个元素增加X，而是将第i个元素增加X * i？但是如果那是列表中的最后一个元素，然后你将其删除会发生什么？当你实际上只应该失去X +最后一个元素时，你会失去i * X。总和就不正确了。 - Jim Mischel

你将第n-i个元素增加x。这将增加元素n-i，n-i+1，.. n的累积频率x。实际总和是累积频率的总和，但如果单独跟踪它，则为O(1)。 - Rusty Rob

0

第174轮比赛的出题人已经发布了本轮的题解。你可以在这里找到它。此外，你还可以查看一些被接受的解决方案：Python, C++。

- welter

当然，每个操作的最优解是O(1)。如果您仍然不理解，我可以尝试更详细地解释一下，但我认为给出的解决方案非常简单。 - welter

我读了这个教程，但是他们的解释对我来说不太清楚，大部分的解决方案代码都很晦涩难懂。虽然Python的解决方案确实非常好。 - Gustavo Torres

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- jacobm · Accepted Answer

你考虑过使用链表加上当前长度和总和吗？对于每个操作，你可以通过额外的常数工作来维护当前平均值（你知道列表的长度和总和，并且所有操作以恒定的方式改变这两个值）。

唯一的非常数操作是将一个常数添加到任意前缀中，这将需要与前缀大小成比例的时间，因为你需要调整每个数字。

要使所有操作都是常数（平摊），需要更多的工作。不要使用双向链表，而是用堆栈支持数组。现在，数组中的每个插槽 i 包含 i 处的数字和要添加到每个元素直至 i 的常数。（请注意，如果你说“将 3 添加到第 11 个元素之前的每个元素”，插槽 11 将包含数字 3，但插槽 0-10 将为空。）现在，每个操作都与之前相同，只是附加新元素涉及标准数组加倍技巧，并且当你从队列末尾弹出最后一个元素时，你需要 (a) 在该插槽中添加常数，以及 (b) 将插槽 i 的常数值添加到插槽 i-1 的常数值中。所以对于你的例子：

添加 0：[(0,0)], 总和 0，长度 1

添加 5：[(0,0),(5,0)], 总和 5，长度 2

添加 6：[(0,0),(5,0),(6,0)], 总和 11，长度 3

将序列中前两个元素加 3：[(0,0),(5,3),(6,0)], 总和 17，长度 3

检索平均值 5.66

删除最后一个元素 [(0,0),(5,3)], 总和 11，长度 2

检索平均值 5.5

删除最后一个元素 [(0,3)], 总和 3，长度 1

以下是一些用 Java 编写的代码，可以更清楚地说明这个想法：

class Averager {
  private int sum;
  private ArrayList<Integer> elements = new ArrayList<Integer>();
  private ArrayList<Integer> addedConstants = new ArrayList<Integer>();

  public void addElement(int i) {
    elements.add(i);
    addedConstants.add(0);
    sum += i;
  }

  public void addToPrefix(int k, int upto) {
    addedConstants.set(upto, addedConstants.get(upto) + k);
    sum += k * (upto + 1);
    // Note: assumes prefix exists; in real code handle an error
  }

  public int pop() {
    int lastIndex = addedConstants.length() - 1;

    int constantToAdd = addedConstants.get(lastIndex);
    int valueToReturn = elements.get(lastIndex);
    addedConstants.set(
      lastIndex-1,
      addedConstants.get(lastIndex-1) + constantToAdd);
    sum -= valueToReturn;
    elements.remove(lastIndex);
    addedConstants.remove(lastIndex);
    return valueToReturn + constantToAdd;
    // Again you need to handle errors here as well, particularly where the stack
    // is already empty or has exactly one element
  }

  public double average() {
    return ((double) sum) / elements.length();
  }
}