如何对整数数组进行预处理，以求出O(1)中任意子数组的平均值？

Question

这个问题改写了一个interview question。由于这个原始问题对我来说似乎太难了，所以我正在尝试解决一个更简单的问题:如何处理整数数组，以在固定时间内找到任何子数组的平均值。显然，我们可以处理O(n^2)中的所有子数组。有没有更好的解决方案？

Answer 1

对于一维情况:计算数组的累积和，即给定数组a，通过以下方式定义b

b[0] = a[0];
for (int i = 1; i < n; ++i)
    b[i] = b[i - 1] + a[i];

为了计算子数组的任何平均值，计算对应于结束索引的累积和与对应于起始索引的累积和的差，并除以子数组中的条目数。例如，对于从i+1到j的范围，执行以下操作

average = (b[j] - b[i]) / (double)(j - i);

同样的事情在二维中也可以通过计算两个轴上的累加和来实现。

Answer 2

我将使用每个子数组的索引0(或一个新的具有参差数组第一维长度的一维数组)来存储平均值，并在将元素添加到数组时计算该平均值。在给定N个项目和+1个项目的平均值的情况下，通过将现有平均值与组成它的N个项目加权，可以在固定时间内计算N+1项目的平均值。这意味着填充数组仍然是线性的，一旦填充，就会得到索引内存中的平均值(有效的恒定时间检索)。

编辑：常量时间平均法不仅仅是“非常接近”；它可以从数学上证明N项乘以N，再加上另一项除以N+1的平均值在一般情况下恰好等于N+1项的平均值。集合S的平均值乘以它的基数N，等于集合S的总和，因此对于基数N的任何非空集S：

avg(S) = sum(S) / count(S)
S' = S + {X}
avg(S') = sum(S') / count(S')
        = (sum(S) + X) / count(S')
        = ((avg(S) * N) + X) / count(S') //QED

再次编辑： Oops:我的解决方案是多维交错数组。好吧，没什么大不了的。在本例中，我将创建一个数组，其中包含从第一个元素到当前元素的所有元素的每个元素的累积和。然后，要计算任何连续子数组的平均值，请从结束索引的累积和中减去开始索引之前的元素的累积和(如果从第一个索引开始，则为零)，然后除以开始索引和结束索引之间的差加1。

..。这就是斯文的答案。