【差分】详解二维前缀和和差分问题

文章目录

  • 1. 二维前缀和
  • 2. 公式推导
  • 3. LeetCode 304 二维区域和检索 - 矩阵不可变
    • 3.1 304 二维区域和检索 - 矩阵不可变
    • 3.2 LeetCode 1139 最大的以 1 为边界的正方形
  • 4. 二维差分问题
  • 5. 二维差分的原理以及差分数组计算
  • 6. 题目
    • 6.1 牛客二维差分
    • 6.2 LeetCode 2132. 用邮票贴满网格图
    • 6.3 LeetCode LCP74 最前祝福立场

1. 二维前缀和

首先来看下二维前缀和，假设现在有下面的二维数组：
在这里插入图片描述

现在设定 sum[i][j] 表示以 (i，j) 为右下角顶点，以（0，0）为左上角顶点的矩形的总和，比如 sum[0][0] = 1，sum[1][1] = 12 … 根据这个定义，现在给一下 sum 数组的结构。
在这里插入图片描述
下面就看下这个 sum 是如何计算出来的，现在先给一下公式：sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + arr[i][j]，为了方便计算，首先我们将第一行和第一列初始化了，因为公式里面有一个 i-1 和 j-1，所以为了避免下标越界，先初始化第一行和第一列，这样后续就从 i = 1，j = 1 开始计算。
在这里插入图片描述
然后开始计算下面的格子：

  • sum[1][1] = sum[0][1] + sum[1][0] - sum[0][0] + arr[1][1] = 12
  • sum[1][2] = sum[0][2] + sum[1][1] - sum[0][1] + arr[1][2] = 21
  • sum[2][1] = sum[2][0] + sum[1][1] - sum[1][0] + arr[2][1] = 27
  • sum[2][2] = sum[1][2] + sum[2][1] - sum[1][1] + arr[2][2] = 45

在这里插入图片描述


2. 公式推导

以 sum[2][2] 为例子，下面图中蓝色部分代表 sum[2][1]，绿色部分代表 sum[1][2]，红色部分代表 sum[1][1]。
在这里插入图片描述
可以看到，sum[2][1] + sum[1][2] 重复添加了红色的部分，所以需要减去 sum[1][1]，最后再把 arr[2][2] 加上，就得到最终的答案了：sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + arr[i][j]。

为了避免下标越界的判断，我们创建 sum 数组的时候让数组长度 + 1，同时改变下定义：sum[i][j] 表示从 (0，0) 到 (i-1，j-1) 这个范围的矩阵的总和。
在这里插入图片描述
然后就不需要先初始化好了第一行和第一列了，可以直接用 sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + arr[i][j] 来设置前缀和数组。


3. LeetCode 304 二维区域和检索 - 矩阵不可变

3.1 304 二维区域和检索 - 矩阵不可变

  • LeetCode 304 二维区域和检索 - 矩阵不可变
class NumMatrix {int[][] sum = null;public NumMatrix(int[][] matrix) {int m = matrix.length;int n = matrix[0].length;sum = new int[m + 1][n + 1];for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + matrix[i - 1][j - 1];}}}public int sumRegion(int row1, int col1, int row2, int col2) {return sum[row2 + 1][col2 + 1] - sum[row1][col2 + 1] - sum[row2 + 1][col1] + sum[row1][col1];}
}

3.2 LeetCode 1139 最大的以 1 为边界的正方形

  • LeetCode 1139 最大的以 1 为边界的正方形
class Solution {public int largest1BorderedSquare(int[][] grid) {int m = grid.length;int n = grid[0].length;int[][] arr = new int[m + 1][n + 1];for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {arr[i][j] = arr[i - 1][j] + arr[i][j - 1] - arr[i - 1][j - 1] + grid[i - 1][j - 1];}}int max = 0;int len = Math.min(m, n);for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {int min = Math.min(len, Math.min(m - i, n - j));for (int k = 1; k <= min; k++) {// 计算四条边长, 也可以计算这个正方形的累加和 - 内部的累加和是否等于周长, 也就是(a, b, c, d) - (a + 1, b + 1, c - 1, d - 1) 的累加和// 这也比较方便if (arr[i + 1][j + k] - arr[i + 1][j] - arr[i][j + k] + arr[i][j] != k) {continue;}if (arr[i + k][j + 1] - arr[i + k][j] - arr[i][j + 1] + arr[i][j] != k) {continue;}if (arr[i + k][j + k] - arr[i + k - 1][j + k] - arr[i + k][j] + arr[i + k - 1][j] != k) {continue;}if (arr[i + k][j + k] - arr[i + k][j + k - 1] - arr[i][j + k] + arr[i][j + k - 1] != k) {continue;}max = Math.max(max, k * k);if(max == len * len){return max;}}}}return max;}
}

这里通过四次计算计算 4 条边长是不是都为 1 来判断这个正方形是不是合规的，更简单的做法是直接将这个边长的正方形的二维前缀和 - 正方形内部的前缀和，求出周长，然后再通过 k 算出周长对比就能知道正方形是不是合规，这种方式更简单。


4. 二维差分问题

首先就是二维差分，在一维差分的基础上，二维差分就是说给定一个区域 [i1，j1] -> [i2，j2] ，然后这个区域内的每个下标都加上一个数字，经过 k 次操作之后，这个二维数组会变成什么样。为什么要用二维差分，因为如果不用差分，每一次操作都需要遍历这个范围去加上数字，这样 k 次操作之后的时间复杂度就是 O(k * m * n)，但是用差分，每一次操作只需要四个步骤，最后再用前缀和处理差分数组，整个过程时间复杂度是 O(m * n)。
在这里插入图片描述
还是以上面的二维数组为例子，假设现在需要做 3 个操作：

  • 给 [0，0] -> [1，1] 范围内的数字 + 3
  • 给 [1，1] -> [2，2] 范围内的数字 - 5
  • 给 [0，0] -> [2，1] 范围内的数字 + 4

最终结果如下：
在这里插入图片描述

现在来说下二维差分的步骤，假设要给 [x1，y1] -> [x2，y2] 这个范围的数字 + v，那么四个步骤：

  • d[x1][y1] += v
  • d[x2 + 1][y1] -= v
  • d[x1][y2 + 1] -= v
  • d[x2+1][y2+1] -= v

什么意思呢，看下面图解。
在这里插入图片描述
做完这几个步骤之后，将这个差分数 d 进行前缀和处理，然后再添加回原数组，就算是完成了。
在这里插入图片描述


5. 二维差分的原理以及差分数组计算

原理也很简单，首先要从前缀和入手，要想让一个区域的下标统一 ± v，这种情况下用前缀和是最简单的，如果考虑前缀和的情况下，就需要每一个格子对其他格子的影响，比如下面的例子。
在这里插入图片描述
当我们要给 [0，0] -> [1，1] 范围内的数字 + 3 时，首先就是设置 d[0][0] + 3，考虑到 d[0][0] 这个位置会影响到整个二维数组的前缀和，也就是这里加了 3 之后计算前缀和时其他格子全部都要 + 3，而我们的目标只是 [0，0] -> [1，1] 这个范围，因此我们需要通过：

  • d[2][0] - 3 消除 [2，0] -> [2，2] 的影响
  • d[0][2] - 3 消除 [0，2] -> [2，2] 的影响

但是消除影响之后明显能发现，右下角以 [2，2] 为右上角的区域重复消除了，所以需要在 d[2][2] + 3 来抵消掉重复消除，最终就是这四个步骤了。

  • d[x1][y1] += v
  • d[x2 + 1][y1] -= v
  • d[x1][y2 + 1] -= v
  • d[x2+1][y2+1] -= v

经过这几个步骤，再求前缀和就能得到 k 次操作的影响，然后添加回原数组就行了。大家也可以注意下，这里我们算影响范围算前缀和的时候没有让 i，j 都 + 1，也就是没有像第 3 小节那个题目那样计算前缀和，因为 d 数组本身为了不越界需要 + 1 处理，所以为了方便计算，前缀和也没有 + 1，只是在原来的数组上进行前缀和，也就是定义 sum[i][j] 为以 i，j 为右下角的区域的前缀和。

如果不想要添加回原数组，可以直接通过原始数组求出差分数组来计算，差分数组计算公式是：d[i][j] = arr[i][j] - arr[i-1][j] - arr[i][j-1] + arr[i-1][j-1]，是通过原始数组计算出来的。计算出差分数组之后可以通过前缀和直接算出原始数组，这样在解题的时候就可以把最后一步添加回原数组去掉了，就比如下面的计算，只是下面题目用的都是不计算差分数组的方式，所以注意下。
在这里插入图片描述


6. 题目

题目来自左神的题单，算法讲解048【必备】二维前缀和、二维差分、离散化技巧

6.1 牛客二维差分

  • 【模板】二维差分

import java.util.*;
import java.lang.*;public class Main {static int n = 0, m = 0, q = 0;static long[][] arr = null;static long[][] d = null;public static void main(String[] args) {Scanner in = new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextInt()) { // 注意 while 处理多个 casen = in.nextInt();m = in.nextInt();q = in.nextInt();arr = new long[n][m];d = new long[n + 1][m + 1];for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {arr[i][j] = in.nextInt();}}for (int i = 0; i < q; i++) {int x1 = in.nextInt() - 1;int y1 = in.nextInt() - 1;int x2 = in.nextInt() - 1;int y2 = in.nextInt() - 1;int v = in.nextInt();d[x1][y1] += v;d[x1][y2 + 1] -= v;d[x2 + 1][y1] -= v;d[x2 + 1][y2 + 1] += v;}}// 对 d 求前缀和for(int i = 0; i <= n; i++){for(int j = 0; j <= m; j++){d[i][j] += getNum(i, j - 1) + getNum(i - 1, j) - getNum(i - 1, j - 1);}}// 加回原数组for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){arr[i][j] += d[i][j];System.out.print(arr[i][j] + " ");}System.out.println();}}public static long getNum(int x, int y) {if (x < 0 || y < 0) {return 0;} else {return d[x][y];}}}

6.2 LeetCode 2132. 用邮票贴满网格图

  • LeetCode 2132. 用邮票贴满网格图
class Solution {public boolean possibleToStamp(int[][] grid, int stampHeight, int stampWidth) {int m = grid.length;int n = grid[0].length;int[][] preSum = new int[m + 1][n + 1];for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1] - preSum[i - 1][j - 1] + grid[i - 1][j - 1];}}int[][] arr = new int[m + 2][n + 2];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == 0 && m - i >= stampHeight && n - j >= stampWidth) {// 如果 stampHeight * stampWidth 区域内都是 0 就说明可以贴if (preSum[i + stampHeight][j + stampWidth] - preSum[i + stampHeight][j] - preSum[i][j + stampWidth] + preSum[i][j] == 0) {// arr 数组 + 2 是因为上下左右都用 0 包围起来了// 差分数组的处理, 区域内左上角 + 1, 区域外(右边 - 1, 下边 - 1, 右下角 + 1)arr[i + 1][j + 1] += 1;arr[i + stampHeight + 1][j + 1] -= 1;arr[i + 1][j + stampWidth + 1] -= 1;arr[i + stampHeight + 1][j + stampWidth + 1] += 1;}}}}// 处理差分数组for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {// 差分数组每个格子 左 + 上 - 左上 + 自己arr[i][j] = arr[i - 1][j] + arr[i][j - 1] - arr[i - 1][j - 1] + arr[i][j];}}// 将差分数组和原数组做对比for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (grid[i - 1][j - 1] == 0 && arr[i][j] == 0) {return false;}}}return true;}}

可以看到这里用的二维前缀和定义做了 + 1处理，也就是 int[][] preSum = new int[m + 1][n + 1]，所以接下来求 d 差分数组的时候为了避免越界也进行了 + 2 处理，但是这样写起来就比较乱，所以涉及到差分的前缀和还是直接根据 6.1 的方式来写比较好。


6.3 LeetCode LCP74 最前祝福立场

  • LeetCode LCP74 最前祝福立场
class Solution {
// 离散化: (x, y, r) -> 左边界, 右边界 = (2x - r, 2x + r), 上边界, 下边界 = (2y + r, 2y - r)public int fieldOfGreatestBlessing(int[][] forceField) {List<Long> listX = new ArrayList<>();List<Long> listY = new ArrayList<>();for (int[] arr : forceField) {long x = arr[0] * 1L;long y = arr[1] * 1L;long r = arr[2] * 1L;listX.add(2 * x - r);listX.add(2 * x + r);listY.add(2 * y - r);listY.add(2 * y + r);}Collections.sort(listX);Collections.sort(listY);listX = listX.stream().distinct().collect(Collectors.toList());listY = listY.stream().distinct().collect(Collectors.toList());int n = listX.size();int m = listY.size();int[][] as = new int[m + 2][n + 2];for (int[] arr : forceField) {int x = arr[0];int y = arr[1];int r = arr[2];int lx = search(2L * x - r, listX);int rx = search(2L * x + r, listX);int dy = search(2L * y - r, listY);int uy = search(2L * y + r, listY);as[dy + 1][lx + 1] += 1;as[uy + 2][lx + 1] -= 1;as[dy + 1][rx + 2] -= 1;as[uy + 2][rx + 2] += 1;}int ans = 0;for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {as[i][j] += as[i - 1][j] + as[i][j - 1] - as[i - 1][j - 1];ans = Math.max(ans, as[i][j]);}}return ans;}public int search(long target, List<Long> list) {int left = 0, right = list.size() - 1;while (left <= right) {int mid = left + ((right - left) >> 1);if (list.get(mid) > target) {right = mid - 1;} else if (list.get(mid) < target) {left = mid + 1;} else {return mid;}}return -1;}
}





如有错误，欢迎指出！！！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.pswp.cn/bicheng/84195.shtml

如若内容造成侵权/违法违规/事实不符，请联系多彩编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

Unity 大型手游碰撞性能优化指南

Unity 大型手游碰撞性能优化指南

Unity 大型手游碰撞性能优化指南 版本: 2.1 作者: Unity性能优化团队 语言: 中文 前言 在Unity大型手游的开发征途中，碰撞检测如同一位隐形的舞者，它在游戏的物理世界中赋予物体交互的灵魂。然而，当这位舞者的舞步变得繁复冗余时，便会悄然消耗宝贵的计算资源，导致帧率下…
阅读更多...
【hive】函数集锦：窗口函数、列转行、日期函数

【hive】函数集锦：窗口函数、列转行、日期函数

窗口函数 https://www.cnblogs.com/Uni-Hoang/p/17411313.html <窗口函数> OVER ([PARTITION BY <分组列> [, <分组列>...]][ORDER BY <排序列> [ASC | DESC] [, <排序列> [ASC | DESC]]...][<rows or range clause>]) )窗口函数主要是…
阅读更多...
DAY 25 异常处理

DAY 25 异常处理

目录 DAY 25 异常处理1.异常处理机制2.debug过程中的各类报错3.try-except机制4.try-except-else-finally机制作业&#xff1a;理解今日的内容即可&#xff0c;可以检查自己过去借助ai写的代码是否带有try-except机制&#xff0c;以后可以尝试采用这类写法增加代码健壮性。 DAY…
阅读更多...
几何绘图与三角函数计算应用

几何绘图与三角函数计算应用

几何绘图与三角函数计算应用 设计思路 左侧为绘图控制面板&#xff0c;右侧为绘图区域支持绘制点、线、矩形、圆、多边形等基本几何图形实现三角函数计算器&#xff08;正弦、余弦、正切等&#xff09;包含角度/弧度切换和常用数学常数历史记录功能保存用户绘图 完整实现代码…
阅读更多...
CSS 定位：原理 + 场景 + 示例全解析

CSS 定位：原理 + 场景 + 示例全解析

一. 什么是CSS定位? CSS中的position属性用于设置元素的定位方式,它决定了元素在页面中的"定位行为" 为什么需要定位? 常规布局(如 display: block)适用于主结构 定位适用于浮动按钮,弹出层,粘性标题等场景帮助我们精确控制元素在页面中的位置 二. 定位类型全…
阅读更多...
GESP 二级复习参考 A

GESP 二级复习参考 A

本教程完整包含&#xff1a; 5000字详细知识点解析 36个Python/C双语言示例 15个GESP真题及模拟题 8张专业图表和流程图 # C编程二级标准终极教程## 一、计算机存储系统深度解析### 1.1 存储体系架构 mermaid graph TDA[CPU寄存器] --> B[L1缓存 1-2ns]B --> C[L2缓…
阅读更多...
嵌入式面试常问问题

嵌入式面试常问问题

以下内容面向嵌入式/系统方向的初学者与面试备考者，全面梳理了以下几大板块，并在每个板块末尾列出常见的面试问答思路，帮助你既能夯实基础，又能应对面试挑战。 一、TCP/IP 协议 1.1 TCP/IP 五层模型概述 链路层（Link Layer） 包括网卡驱动、以太网、Wi‑Fi、PPP 等。负责…
阅读更多...
【人工智能 | 项目开发】Python Flask实现本地AI大模型可视化界面

【人工智能 | 项目开发】Python Flask实现本地AI大模型可视化界面

文末获取项目源码。 文章目录 项目背景项目结构app.py（后端服务）index.html（前端界面）项目运行项目图示项目源码项目背景 随着人工智能技术的快速发展，大语言模型在智能交互领域展现出巨大潜力。本项目基于 Qwen3-1.7B 模型，搭建一个轻量化的智能聊天助手，旨在为用户提…
阅读更多...
【设计模式】1.简单工厂、工厂、抽象工厂模式

【设计模式】1.简单工厂、工厂、抽象工厂模式

every blog every motto: You can do more than you think. https://blog.csdn.net/weixin_39190382?typeblog 0. 前言 以下是 简单工厂模式、工厂方法模式 和 抽象工厂模式 的 Python 实现与对比&#xff0c;结合代码示例和实际应用场景说明&#xff1a; 1. 简单工厂模式&a…
阅读更多...
浏览器访问 AWS ECS 上部署的 Docker 容器（监听 80 端口）

浏览器访问 AWS ECS 上部署的 Docker 容器（监听 80 端口）

✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义&#xff08;Task Definition&…
阅读更多...
01.SQL语言概述

01.SQL语言概述

SQL 语言概述 SQL &#xff08;Structured Query Language&#xff09;结构化査询语言 1. 关系型数据库的常见组件 数据库: database 表的集合&#xff0c;物理上表现为一个目录表: table&#xff0c;行: row 列: column索引: index视图: view&#xff0c;虚拟的表存储过程:…
阅读更多...
C++学习-入门到精通【14】标准库算法

C++学习-入门到精通【14】标准库算法

C学习-入门到精通【14】标准库算法 目录 C学习-入门到精通【14】标准库算法一、对迭代器的最低要求迭代器无效 二、算法1.fill、fill_n、generate和generate_n2.equal、mismatch和lexicographical_compare3.remove、remove_if、remove_copy和remove_copy_if4.replace、replace_…
阅读更多...
Vue 项目实战：三种方式实现列表→详情页表单数据保留与恢复

Vue 项目实战：三种方式实现列表→详情页表单数据保留与恢复

背景&#xff1a;在Vue项目中&#xff0c;实现列表页跳转详情页并保留表单数据&#xff0c;返回时恢复表单状态。 核心功能&#xff1a; 保存缓存&#xff1a;点击查询按钮时&#xff0c;表单数据保存恢复缓存&#xff1a;从详情页返回时&#xff0c;恢复表单数据清除缓存&…
阅读更多...
iptables实验

iptables实验

实验一&#xff1a;搭建web服务&#xff0c;设置任何人能够通过80端口访问。 1.下载并启用httpd服务器 dnf -y install httpd 开启httpd服务器 systemctl start httpd 查看是否启用 下载并启用iptables&#xff0c;并关闭firewalld yum install iptable…
阅读更多...
Razor编程RenderXXX相关方法大全

Razor编程RenderXXX相关方法大全

文章目录 第一章&#xff1a;RenderXXX方法概述1.1 RenderXXX方法的作用与意义1.2 基本工作原理1.3 主要方法分类 第二章&#xff1a;部分视图渲染方法2.1 Html.RenderPartial()2.2 Html.RenderAction()2.3 性能对比分析 第三章&#xff1a;视图组件渲染方法3.1 Html.RenderCom…
阅读更多...
Go 语言 range 关键字全面解析

Go 语言 range 关键字全面解析

Go 语言 range 关键字全面解析 range 是 Go 语言中用于迭代数据结构的关键字&#xff0c;支持多种数据类型的遍历操作。它提供了一种简洁、安全且高效的方式来处理集合类型的数据。 基本语法 for index, value : range collection {// 循环体 } 1. 数组/切片迭代 fruits :…
阅读更多...
美化显示LLDB调试的数据结构

美化显示LLDB调试的数据结构

前面的博文美化显示GDB调试的数据结构介绍了如何美化显示GDB中调试的数据结构&#xff0c;本文将还是以mupdf库为例介绍如何美化显示LLDB中调试的数据结构。 先看一下美化后的效果&#xff1a; 一、加载自定义脚本 与GDB类似&#xff0c;需要添加一个~/.lldbinit文件&#xf…
阅读更多...
【Java学习笔记】日期类

【Java学习笔记】日期类

日期类 第一代日期类&#xff1a;Date 引入包 import java.text.ParseException&#xff1a;日期转换可能会抛出转换异常 import java.text.SimpleDateFormat import java.util.Date 1. 基本介绍 Date&#xff1a;精确到毫秒&#xff0c;代表特定的瞬间 SimpleDateForma…
阅读更多...
C++基础进阶：函数、内联函数与Lambda函数详解

C++基础进阶：函数、内联函数与Lambda函数详解

引言 在C编程的旅程中&#xff0c;函数是构建复杂程序的基本单元。它们像乐高积木一样&#xff0c;允许我们将代码分解成更小、更易于管理的部分。今天&#xff0c;我们将深入探讨C中的三种重要函数类型&#xff1a;普通函数、内联函数以及Lambda函数。掌握它们&#xff0c;将…
阅读更多...
从Node.js到React/Vue3：流式输出技术的全栈实现指南

从Node.js到React/Vue3：流式输出技术的全栈实现指南

本文将从底层原理到工程实践&#xff0c;完整解析如何使用Node.js后端结合React和Vue3前端实现流式输出功能&#xff0c;涵盖协议选择、性能优化、错误处理等关键细节&#xff0c;并通过真实场景案例演示完整开发流程。 一、流式输出的核心原理与协议选择 1.1 流式传输的底层机…
阅读更多...
最新文章

Copyright @ 2022~2023