algorithm - 如何处理整数矩阵以求 O(1) 中任意子矩形元素的平均值？

Question

这是一个 interview question :如何处理一个整数矩阵来求 O(1) 中任意子矩形元素的平均值？正如评论所说，我们应该计算前缀和。

好吧，这很尴尬，但即使问了类似的问题question我不明白。

Answer 1

虽然你有几个合理的答案，但这似乎是一个图片值几千字的问题。

好的——我们想要的是矩形 4 的面积。然而，我们预先计算的面积只告诉我们使用从左上角的原点开始的整个矩形的面积，并且延伸到 4 的右下角。要仅计算 4 的面积，我们必须减去上方和左侧的面积(1、2 和 3)。 2 和 3 的区域是一样的:我们只能得到它们的区域从左上角开始延伸到右下角。这意味着我们可以获得它们的面积之和，但是矩形 1 的面积包含在两者中。

因此，要获得矩形 4 的面积，我们需要找到其右下角的面积。我们找到 2 和 3 右下角的区域并将它们相加。然后我们减去矩形 1 右下角的面积，因为它被包含在我们的总数中两次。这给出了矩形 1、2 和 3 的总面积。我们从矩形 4 右下角的面积中减去它，得到矩形 4 本身的面积。

举个例子，假设我设法让所有这些矩形都具有相同的大小，所以我们将每个“1”的区域称为该区域。因此，每个矩形右下角的面积为:

1. 1
2. 2
3. 2
4. 4

为简单起见，我们将每个定义为 pc_area(x)(即我们将在矩形 x 的右下角获得的预计算区域)。

因此，我们采用:pc_area(4) - (pc_area(2) + pc_area(3) - pc_area(1))代入数字，我们得到:4 - (2 + 2 -1)，或 4-3，这显然给出了 1，即我们最初定义为正确的答案。