二维静态前缀和
二维静态前缀和
二维静态前缀和是一维前缀和在二维平面上的扩展，用于快速计算矩阵中任意子矩阵的元素和。
通过预处理，可以将子矩阵求和的时间复杂度从 优化到
。
基本概念
二维前缀和的核心思想是：
- 预处理矩阵，计算前缀和数组
- 前缀和数组的 prefix[i][j] 表示左上角为
，右下角为
的子矩阵和
- 任意子矩阵的和可以通过容斥原理计算
- 适用于频繁查询子矩阵和的场景
实现方式
二维前缀和的实现步骤：
- 创建前缀和数组（通常比原数组多一行一列）
- 预处理计算前缀和
- 使用容斥原理计算子矩阵和
基本实现
class PrefixSum2D {
private:
vector<vector<int>> prefix;
public:
PrefixSum2D(vector<vector<int>>& matrix) {
if (matrix.empty() || matrix[0].empty()) return;
int m = matrix.size(), n = matrix[0].size();
prefix.resize(m + 1, vector<int>(n + 1));
// 计算二维前缀和
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1]
+ matrix[i-1][j-1];
}
}
}
// 查询子矩阵和 [(x1,y1), (x2,y2)]
int sumRegion(int x1, int y1, int x2, int y2) {
return prefix[x2+1][y2+1] - prefix[x2+1][y1] - prefix[x1][y2+1]
+ prefix[x1][y1];
}
};
class PrefixSum2D {
private int[][] prefix;
public PrefixSum2D(int[][] matrix) {
if (matrix.length == 0 || matrix[0].length == 0) return;
int m = matrix.length, n = matrix[0].length;
prefix = new int[m + 1][n + 1];
// 计算二维前缀和
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1]
+ matrix[i-1][j-1];
}
}
}
// 查询子矩阵和 [(x1,y1), (x2,y2)]
public int sumRegion(int x1, int y1, int x2, int y2) {
return prefix[x2+1][y2+1] - prefix[x2+1][y1] - prefix[x1][y2+1]
+ prefix[x1][y1];
}
}
class PrefixSum2D:
def __init__(self, matrix):
if not matrix or not matrix[0]:
return
m, n = len(matrix), len(matrix[0])
self.prefix = [[0] * (n + 1) for _ in range(m + 1)]
# 计算二维前缀和
for i in range(1, m + 1):
for j in range(1, n + 1):
self.prefix[i][j] = (self.prefix[i-1][j] +
self.prefix[i][j-1] -
self.prefix[i-1][j-1] +
matrix[i-1][j-1])
# 查询子矩阵和 [(x1,y1), (x2,y2)]
def sum_region(self, x1, y1, x2, y2):
return (self.prefix[x2+1][y2+1] - self.prefix[x2+1][y1] -
self.prefix[x1][y2+1] + self.prefix[x1][y1])
应用场景
二维前缀和在很多问题中都有应用：
- 子矩阵和查询
- 图像处理
- 热力图计算
- 地图区域统计
- 优化动态规划
示例：最大正方形
int maximalSquare(vector<vector<char>>& matrix) {
if (matrix.empty() || matrix[0].empty()) return 0;
int m = matrix.size(), n = matrix[0].size();
vector<vector<int>> prefix(m + 1, vector<int>(n + 1));
// 计算二维前缀和
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1]
+ (matrix[i-1][j-1] - '0');
}
}
int maxSide = 0;
// 枚举所有可能的正方形
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
for (int k = maxSide + 1; k <= min(i, j); k++) {
int sum = prefix[i][j] - prefix[i-k][j] - prefix[i][j-k]
+ prefix[i-k][j-k];
if (sum == k * k) {
maxSide = k;
} else {
break;
}
}
}
}
return maxSide * maxSide;
}
public int maximalSquare(char[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
int m = matrix.length, n = matrix[0].length;
int[][] prefix = new int[m + 1][n + 1];
// 计算二维前缀和
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1]
+ (matrix[i-1][j-1] - '0');
}
}
int maxSide = 0;
// 枚举所有可能的正方形
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
for (int k = maxSide + 1; k <= Math.min(i, j); k++) {
int sum = prefix[i][j] - prefix[i-k][j] - prefix[i][j-k]
+ prefix[i-k][j-k];
if (sum == k * k) {
maxSide = k;
} else {
break;
}
}
}
}
return maxSide * maxSide;
}
def maximalSquare(self, matrix: List[List[str]]) -> int:
if not matrix or not matrix[0]:
return 0
m, n = len(matrix), len(matrix[0])
prefix = [[0] * (n + 1) for _ in range(m + 1)]
# 计算二维前缀和
for i in range(1, m + 1):
for j in range(1, n + 1):
prefix[i][j] = (prefix[i-1][j] + prefix[i][j-1] -
prefix[i-1][j-1] + int(matrix[i-1][j-1]))
max_side = 0
# 枚举所有可能的正方形
for i in range(1, m + 1):
for j in range(1, n + 1):
for k in range(max_side + 1, min(i, j) + 1):
sum_val = (prefix[i][j] - prefix[i-k][j] -
prefix[i][j-k] + prefix[i-k][j-k])
if sum_val == k * k:
max_side = k
else:
break
return max_side * max_side
时间复杂度
- 预处理：
- 查询：
- 空间复杂度：
二维前缀和的优缺点
优点：
- 子矩阵查询
时间复杂度
- 实现相对简单
- 适用于多次查询
缺点：
- 只适用于静态矩阵
- 需要额外空间
- 不支持修改操作
注意事项
- 正确处理边界情况
- 注意容斥原理的应用
- 处理空矩阵的情况
- 考虑整数溢出问题
练习建议
- 实现基本的二维前缀和
- 解决子矩阵相关问题
- 尝试结合其他技巧
- 练习三维前缀和的扩展
经典例题
牛客代码笔记-牛栋 文章被收录于专栏
汗牛充栋，学海无涯。<br/> 内含算法知识点讲解，以及牛客题库精选例题。<br/> 学习算法，从牛栋开始。
投递库洛游戏等公司6个岗位 >