有效地计算矩阵中元素的总和

在一次采访中，有人问我是否得到了一个n * m矩阵，该矩阵如何计算给定子矩阵（由左上，右下坐标定义）中的值之和。

有人告诉我可以对矩阵进行预处理。

有人告诉我矩阵可能很大，子矩阵也可能很大，因此算法必须高效。我绊了一下，却没有被告知最佳答案。

有人有很好的答案吗？

这就是汇总面积表的用途。

http://en.wikipedia.org/wiki/Summed_area_table

您的“预处理”步骤是构建一个大小相同的新矩阵，其中每个条目都是该条目左上角子矩阵的总和。通过查找和混合SAT中的4个条目，可以计算出任意子矩阵和。

这是一个例子。

对于初始矩阵

0 1 4 2 3 2 1 2 7

SAT是

0 1 5 2 6 12 3 9 22

使用S（x，y）= a（x，y）+ S（x-1，y）+ S（x，y-1）-S（x-1，y-1）获得SAT

其中S是SAT矩阵，a是初始矩阵。

如果您想要右下2x2子矩阵的总和，答案将是22 + 0-3-5 =14。这显然与3 + 2 + 2 +

7相同。无论矩阵的大小如何，子矩阵的总和可以在4个查询和3个算术运算中找到。建立SAT是O（n），类似地，每个单元仅需要4次查找和3次数学运算。