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

Question

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

Answer 1

对于1D情况下:计算所述阵列的,即给定阵列的累计总和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);

通过计算沿两个轴的累积和,同样的事情在两个维度上起作用.