更新
仅供以后引用，我将列出所有我知道的统计信息，这些统计信息可以保存在滚动集合中，每次添加/删除时都重新计算为O(1)操作(这实际上是我应该从一开始就说出这个问题):
明显
不太明显
好吧，因此要准确地说:这些并不是我所知道的统计数据的“全部”。我只是现在就想起了它们。
*仅可以在O(1)中重新计算，或者如果对集合进行了排序，则可以在O(1)中重新计算(但是在这种情况下，插入不是O(1))。删除可能会导致对未排序的集合进行O(n)重新计算。
**仅在O(1)中针对已排序的索引集合重新计算。
***需要相当复杂的数据结构才能在O(1)中重新计算。
****当权重以线性下降的方式分配时，这肯定可以在O(1)中实现增加和减少。在其他情况下，我不确定。
原始问题
假设我维护着一组数字数据-假设只有一堆数字。对于此数据，可能有许多计算值可能是您感兴趣的。一个例子就是和。为了获得所有这些数据的总和，我可以...
选项1:遍历集合，添加所有值:
double sum = 0.0;
for (int i = 0; i < values.Count; i++) sum += values[i];
选项2:维持总和，无需遍历集合就可以找到总和:
void Add(double value) {
values.Add(value);
sum += value;
}
void Remove(double value) {
values.Remove(value);
sum -= value;
}
编辑:为了更贴切地讲这个问题，让我们将上面的两个选项与(某种)现实情况进行比较:
假设我开始大声列出数字，并要求您将其保留在脑海中。我首先说:“11、16、13、12”。如果您只是记住数字本身，仅此而已，然后我说:“总和是多少？”，您必须自己思考:“好，11 + 16 + 13 + 12是多少？”在回答“52”之前。另一方面，如果您在我列出数字时一直跟踪自己的总和(即，当我说“11”时，您认为“11”，当我说“16”时，您认为，“27” ，等等)，您可以立即回答“52”。然后，如果我说“好吧，现在忘记数字16”，那么如果您一直在脑海中追踪总和，则可以简单地从52中减去16，然后知道新的总和是36，而不是将16减去列表，他们总结出11 + 13 + 12。
所以我的问题是，除了显而易见的总和和平均值之外，还有哪些其他计算方式呢？
第二编辑:作为(我几乎可以肯定)确实需要迭代的统计信息的任意示例-因此不能简单地将其保持为总和或平均值-考虑一下我是否问过您，“这个集合可以被最小整除吗？”假设数字是5、15、19、20、21、25和30。这组数字的最小值是5，分为5、15、20、25和30(但不是19或21)，所以答案是5。现在，如果我从集合中删除5，并提出相同的问题，答案现在是2，因为新的最小值15仅可将15和30整除；但是，据我所知，如果不再次浏览该集合，就无法知道这一点。
因此，我认为这成为我问题的核心:如果我们可以将各种统计信息划分为这些类别，则那些是可维护的(我自己的说法，也许某个地方更官方)，而不是那些需要迭代来计算任何更改集合时，所有可维护的集合是什么？
我要问的内容与online algorithm并不完全相同(尽管我衷心感谢那些向我介绍了该概念的人)。在线算法甚至可以在没有看到所有输入数据的情况下开始工作。我所寻求的可维护统计信息肯定会看到所有数据，只要它们改变就不需要一遍又一遍地重申。
最佳答案
首先，您要在此处使用的术语是online algorithm。可以在线计算所有moments(平均值，标准偏差，偏斜等)。其他包括最小值和最大值。请注意，不能在线计算中值和mode。
关于language-agnostic - 无需迭代即可为一组数字数据维护哪些统计信息？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/1574303/