如何高效统计二进制矩阵指定子矩阵中1的数量？

你猜的没错，前缀和矩阵就是实现O(1)单次查询的最优预计算方案，整体时间复杂度为O(M*N + K)（M、N是原矩阵的行列数，K是查询次数），这是当前能达到的最优复杂度。

前缀和矩阵的构建 #

假设原二进制矩阵为matrix，我们先构建一个大小相同（或多开一行一列边界）的前缀和矩阵prefix，其中prefix[i][j]代表原矩阵从左上角(1,1)到(i,j)的矩形区域内所有1的总数（建议把原矩阵的索引改成从1开始，避免边界判断；如果原矩阵是0索引，就给prefix多设第0行和第0列，值全为0）。

构建公式如下：

prefix[i][j] = matrix[i][j] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1]

公式解释：

• matrix[i][j]：当前位置的二进制值（0或1）
• prefix[i-1][j]：当前位置上方矩形的1总数
• prefix[i][j-1]：当前位置左方矩形的1总数
• 减去prefix[i-1][j-1]：因为上方和左方的矩形重叠了左上角区域，这部分被重复加了两次，需要去重

单次查询的计算方法 #

对于给定的查询子矩阵（左上角(x1,y1)，右下角(x2,y2)），直接用前缀和矩阵计算1的总数：

count = prefix[x2][y2] - prefix[x1-1][y2] - prefix[x2][y1-1] + prefix[x1-1][y1-1]

公式解释：

• prefix[x2][y2]：从(1,1)到(x2,y2)的大矩形1总数
• 减去prefix[x1-1][y2]：去掉子矩阵上方的区域
• 减去prefix[x2][y1-1]：去掉子矩阵左方的区域
• 加上prefix[x1-1][y1-1]：因为左上角的重叠区域被减了两次，需要补回来一次

示例验证 #

比如原矩阵（1索引）：

1 0 1
0 1 0
1 1 1

对应的前缀和矩阵：

1  1  2
1  2  3
2  4  6

查询子矩阵(2,1)到(3,3)，代入公式：
6 - prefix[1][3] - prefix[3][0] + prefix[1][0] = 6 - 2 - 0 + 0 = 4，和实际子矩阵内的1数量（0,1,0,1,1,1共4个1）完全一致。

内容的提问来源于stack exchange，提问作者popcorn