问题描述
在接受采访时有人问我，如果我获得了一个N * M的矩阵如何计算在给定的子矩阵的值的总和（按左上角，右下角坐标定义）。
In an interview I was asked if I was given an n*m matrix how to calculate the sum of the values in a given sub-matrix (defined by top-left, bottom-right coordinates).
我被告知我可以pre-过程中的矩阵。
I was told I could pre-process the matrix.
有人告诉我矩阵可能是巨大的，因此可以将子矩阵使算法中必须是有效的。我迷迷糊糊了一下，没有被告知最好的答案。
I was told the matrix could be massive and so could the sub-matrix so the algo had to be efficient. I stumbled a bit and wasn't told the best answer.
任何人有一个很好的答案？
Anyone have a good answer?
推荐答案
这是什么总结区的表是。 http://en.wikipedia.org/wiki/Summed_area_table
This is what Summed Area Tables are for. http://en.wikipedia.org/wiki/Summed_area_table
您preprocessing的步骤是建立相同的大小，每个条目是子矩阵的总和的一个新的矩阵左上角的条目。任何任意子矩阵和可以通过查找和在SAT混合只有4个条目来计算
Your "preprocessing" step is to build a new matrix of the same size, where each entry is the sum of the sub-matrix to the upper-left of that entry. Any arbitrary sub-matrix sum can be calculated by looking up and mixing only 4 entries in the SAT.
编辑：下面是一个例子
对于初始矩阵
0 1 4
2 3 2
1 2 7
该SAT是
0 1 5
2 6 12
3 9 22
的SAT被使用S（X，Y）= A（X，Y）+ S（X-1，Y）+ S（X，Y-1）中得到 - S（X-1，Y-1）
The SAT is obtained using S(x,y) = a(x,y) + S(x-1,y) + S(x,y-1) - S(x-1,y-1),
其中S是SAT矩阵和是初始矩阵
where S is the SAT matrix and a is the initial matrix .
如果你想右下方2x2子矩阵的总和，答案是22 + 0 - 3 - 5 = 14，这显然是相同的3 + 2 + 2 + 7，无论大小矩阵，子矩阵的总和可以在4查找和3算术OPS中找到。构建SAT是O（n），同样只需要4查找和每单元3数学欢声笑语。
If you want the sum of the lower-right 2x2 sub-matrix, the answer would be 22 + 0 - 3 - 5 = 14. Which is obviously the same as 3 + 2 + 2 + 7. Regardless of the size of the matrix, the sum of a sub matrix can be found in 4 lookups and 3 arithmetic ops. Building the SAT is O(n), similarly requiring only 4 lookups and 3 math ops per cell.
这篇关于有效地计算在矩阵元素之和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！