在一次采访中，有人问我是否得到了一个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次数学运算。
