algorithm - 序列平均值的高效数据结构

Question

我需要设计一个数据结构来有效地支持对存储的(我认为合适的)数字序列进行以下操作:

• 将整数 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 的我需要所有操作的次线性运行时间，因为在最坏的情况下，添加到第一个元素可能与添加到整个序列相同

Answer 1

有没有考虑过用链表加上当前的长度和和？对于每个操作，您可以通过不断的额外工作来维持当前平均值(您知道列表的长度和总和，并且所有操作都会以恒定的方式更改这两个值)。

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

要使所有操作恒定(摊销)恒定需要更多的工作。不使用双向链表，而是用堆栈支持数组。数组中的每个槽 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

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

检索平均值 5.66

移除最后一个元素[(0,0),(5,3)], sum 11, length 2

检索平均值 5.5

移除最后一个元素[(0,3)], sum 3, length 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();
  }
}