有效地计算矩阵中元素的总和
在一次采访中,我被问到是否给了一个n*m矩阵如何计算给定子矩阵中值的总和(由左上角,右下角坐标定义).
我被告知我可以预处理矩阵.
我被告知矩阵可能很大,子矩阵也是如此,因此算法必须高效.我偶然发现了一些并没有被告知最佳答案.
有谁有一个很好的答案？
Ala*_*lan 50
这是Summed Area Tables的用途. 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次数学运算.
- 谢谢艾伦!我从来没有听说过Summed Area Table,我已经编程了18年.我睡觉/喝酒通过大学(我的坏). (4认同)
- 我已经使用*这个想法好几年了,从来没有听说过"总和区域表"的名字 - 写得不好的维基百科文章暗示它是一个特定于计算机视觉/图形领域的名称.对于熟悉动态编程的人来说,这个想法本身是相当自然的 - 也许是太自然了,不值得一个名字. (3认同)
您可以通过动态编程来完成.创建大小为n*m的矩阵dp.并为每个我,j在哪里
1 <= i <= n , 1 <= j <= m
dp[i][j] will be :
dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + values[i][j]
对于每个查询,我们有lx,rx,ly,ry,其中lx和rx是左上角坐标,ly和ry是子矩阵的右下角坐标.
1 ? lxi ? rx ? n, 1 ? ly ? ry ? m
sum = dp[rx][ry] - dp[lx - 1][ry] - dp[rx][ly - 1] + dp[lx-1][ly - 1]
查看图片以了解算法的工作原理.
OD = dp[rx][ry], OB = dp[lx - 1][ry], OC = dp[rx][ly - 1], OA = dp[lx - 1][ly - 1]
