有效计算矩阵中元素的总和 [英] Calculate the sum of elements in a matrix efficiently

问题描述

在一次采访中，有人问我是否给了一个 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).

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

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.

有人有好的答案吗?

推荐答案

这就是总面积表的用途.http://en.wikipedia.org/wiki/Summed_area_table

This is what Summed Area Tables are for. http://en.wikipedia.org/wiki/Summed_area_table

您的预处理"步骤是构建一个相同大小的新矩阵，其中每个条目是该条目左上角的子矩阵的总和.任何任意子矩阵和都可以通过在 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

使用 S(x,y) = a(x,y) + S(x-1,y) + S(x,y-1) - S(x-1,y-1) 获得 SAT,

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 矩阵，a 是初始矩阵.

where S is the SAT matrix and a is the initial matrix .

如果你想要右下角的 2x2 子矩阵的和，答案是 22 + 0 - 3 - 5 = 14.这显然和 3 + 2 + 2 + 7 是一样的.不管大小在矩阵中，子矩阵的总和可以在 4 次查找和 3 次算术运算中找到.构建 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.

这篇关于有效计算矩阵中元素的总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！