我需要设计一个数据结构，它可以有效地支持对存储的(我认为合适的)数字序列的以下操作:
- 将整数
x添加到序列 的第一个 - 在序列 末尾添加一个整数
- 删除序列的最后一个元素
- 检索序列中所有元素的平均值
i元素中k从空序列[]
- 附加0 (
[0]) - 附加5 (
[0, 5]) - 附加6 (
[0, 5, 6]) - 在序列(
[3, 8, 6])的前2个元素上添加3 - 检索平均值5.66 (
[3, 8, 6]) - 删除最后一个元素(
[3, 8]) - 检索平均值5.5 (
[3, 8])
以前的作品
我考虑过使用Fenwick树(Topcoder Editorial)，但为此我需要指定Fenwick树初始化序列的最大大小，这并不一定知道。但是，如果我有一个序列可以支持的最大元素数，那么如果我保存序列中所有元素的和，我就可以支持O(lg N)上的这些操作。
编辑:这个问题是针对一个Codeforces问题，我需要所有操作的子线性运行时间，因为添加到第一个元素可以，在最坏的情况下，与添加到整个序列
你考虑过使用链表加上当前长度和总和吗?对于每一个操作，你都可以用恒定的额外工作来维持当前的平均值(你知道列表的长度和总和，所有的操作都以恒定的方式改变这两个值)。
唯一的非常数操作是向任意前缀添加常数，这将花费与前缀大小成正比的时间，因为您需要调整每个数字。
使所有操作都是常数(平摊)需要做更多的工作。不使用双链表，而是使用堆栈返回数组。数组中的每个槽位i现在既包含i的数字，也包含要添加到i之前的每个元素的常数。(注意，如果你说"在元素11之前的每个元素都加3"，槽11将包含数字3，但槽0-10将是空的。)现在每个操作都和以前一样，除了添加一个新元素涉及到标准的数组加倍技巧，当您从队列的末尾弹出最后一个元素时，您需要(a)在该插槽添加常量，(b)将插槽i的常量值添加到插槽i-1的常量中。对于你的例子:
追加0:[(0,0)], sum 0, length 1
追加5:([(0,0),(5,0)], sum 5, length 2
追加6:[(0,0),(5,0),(6,0)], sum 11, length 3
在序列的前两个元素上加上3:[(0,0),(5,3),(6,0)], sum 17, length 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();
}
}
听起来像是一个双重链表，维护了头部和尾部引用，以及当前的总和和计数。
将整数x加到序列的前i个元素
从*头开始，添加x，下一项。重复i次。sum += i*x
在序列末尾添加一个整数k
从*tail开始，创建头=尾，尾= null的新项目。更新*尾，sum和计数。
删除序列的最后一个元素
将*tail更新为*tail->prev。更新总和，递减计数
检索平均值5.5 ([3,8])
返回sum/count
这个数据结构可以只是一个元组(N, S)，其中N是计数，S是和和一堆数字。没有什么幻想。所有的操作都是O(1)，除了第一个操作是O(i)。
我建议你尝试使用二叉索引树。
它们允许您访问O(Log(n))的累积频率。
您也可以按log(i)的顺序在前i个元素上添加。
但是，不是将前i个元素增加X，而是将第n个元素增加X。
要删除最后一个元素，可能需要另一个树来计算累计删除的元素。(所以不是删除，而是将该数量添加到另一个树中，当访问第一个树时，您总是从结果中减去该数量)
对于追加，我建议您从大小为2*N的树开始这样你就有空间了。如果树的大小大于2*N，就再添加一个2*N大小的树。(不确定最好的方法，但希望你能弄清楚)。
为了满足第一个需求，您可以维护一个单独的添加操作数据结构。基本上，它是范围和增量的有序集合。还要维护这些相加的和。所以，如果你把5加到前3项，然后把12加到前10项，你会得到:
{3, 5}
{10, 12}
这些相加的和是(3*5) + (10*12) = 135。
当被要求提供总和时，你提供项目的总和加上这些相加的总和。
唯一的麻烦是当你从列表中删除最后一项时。然后，您必须遍历这个添加的集合，以找到包含最后一项(您要删除的项)的任何项。该数据结构可以是哈希映射，键是索引。所以在上面的例子中，你的哈希映射应该是:
key: 3 value: 5
key: 10 value: 12
无论何时执行第一个操作，都要检查哈希映射以查看是否已经存在具有该键的项。如果是这样，只需更新那里的值，而不是添加新的增量。并相应地更新总和。
有趣。你甚至不需要保留加法的和。你可以随时更新总金额。
当您从列表中删除最后一个项时，您将检查哈希映射中是否存在具有该键的项。如果有，则删除该项，减少键值，然后将其添加回哈希映射(或者使用该键更新现有项，如果有的话)。
因此，使用mattedgod提出的双链表，并使用他提出的和。然后使用这个哈希映射来维护列表中添加的集合，并相应地更新总和。
第174轮问题解决者已经发表了这一轮的社论。你可以在这里找到。你也可以看看一些公认的解决方案:Python, c++。