arrays - 如何预处理整数数组以找到 O(1) 中任意子数组的平均值？

Question

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

Answer 1

对于 1d 情况:计算数组 i 的累积和。 e.给定数组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);

通过计算沿两个轴的累积和，同样的事情在二维中起作用。