知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 06 - 二维区域和检索 ## 题目(LeetCode 304) 给定一个二维矩阵,多次查询某个矩形区域内元素的总和。 ``` 矩阵: 3 0 1 4 2 5 6 3 2 1 1 2 0 1 5 4 1 0 1 7 1 0 3 0 5 sumRegion(2,1,4,3) = 2+0+1 + 1+0+1 + 0+3+0 = 8 ``` ## 代码 ```java class NumMatrix { private int[][] prefix; public NumMatrix(int[][] matrix) { 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] = matrix[i-1][j-1] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1]; } } } public int sumRegion(int r1, int c1, int r2, int c2) { return prefix[r2+1][c2+1] - prefix[r1][c2+1] - prefix[r2+1][c1] + prefix[r1][c1]; } } ``` ``` 容斥原理图示: prefix[r2+1][c2+1] = 整个大矩形 - prefix[r1][c2+1] = 上方矩形 - prefix[r2+1][c1] = 左方矩形 + prefix[r1][c1] = 左上角(被减了两次,加回来) ┌──────┬──────┐ │ 左上 │ 上 │ ├──────┼──────┤ │ 左 │ 目标 │ └──────┴──────┘ ``` ## 复杂度 - 构建:O(m×n) - 查询:O(1) ## 一句话总结 二维前缀和 = 容斥原理。构建 O(mn),查询 O(1)。 --- 上一篇:[05 - 和可被K整除的子数组](./05-subarray-div-by-k.md) | 返回:[目录](./README.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入