当前位置：首页 > news >正文

算法题（133）：二维差分

news 来源：原创 2025/7/5 9:33:42

审题：
本题需要我们多次对某个矩形区域的数据加k，最后输出加完的数据

思路：
方法一：二维差分

本题涉及的是对二维的区间加同一个数的操作，且只显示一次最终结果，所以我们可以使用差分的方法

二维差分的性质：

1.和一维差分还原方法类似，二维差分的还原方法是从(1,1)开始求f[i][j]的前缀和

2.对某个位置的差分值加k：相当于对前缀和计算时包含该位置的数据索引位置都加了k

图示：图示为差分数组

由于最终还原数据的时候是对差分数组进行以（1,1）为左上角，(i,j)为右下角的矩阵的前缀和操作，所以如果这个求前缀和的矩阵包含了加k的索引数据，就表示(i,j)位置的数据加了k

3.进行二维差分修改和创建的方法

图示1：原二维数组

假设我们对图示的位置数据都加了k，相当于对以（2，3）为左上角，以（3.6）为右下角的矩阵集体进行加k操作

图示2：差分二维数组

首先我们对（2,3）加k，此时表示从(2,3)到(9,9)区域的数据都加了k

由于我们只能对红色区域加k，所以我们要消除（2,3）位置加k对其他位置的影响

第一步：在（2,7）位置-k，消除从（2,7）为左上角（9,9）为右下角的矩阵+k的影响

第二步：在（4,3）位置-k，消除从（4,3）为左上角（9,9）为右下角的矩阵+k的影响

第三步：由于（4,7）为左上角，（9,9）为右下角的矩阵经过两次-k，所以我们还需要加k来消除多减的k的影响

总结：

构建和修改操作:

x1,y1为左上角坐标，x2,y2为右下角坐标

f[x1][y1] += k;
f[x2 + 1][y1] -= k;
f[x1][y2 + 1] -= k;
f[x2 + 1][y2 + 1] += k;

解题：
#include<iostream>
using namespace std;
typedef long long ll;
const int N = 1010;
int n, m, q;
ll f[N][N];//差分数组
int main()
{cin >> n >> m >> q;//预处理差分数组for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){ll num;cin >> num;f[i][j] += num;f[i + 1][j] -= num;f[i][j + 1] -= num;f[i + 1][j + 1] += num;}}//修改差分while (q--){ll x1, x2, y1, y2, k;cin >> x1 >> y1 >> x2 >> y2 >> k;f[x1][y1] += k;f[x2 + 1][y1] -= k;f[x1][y2 + 1] -= k;f[x2 + 1][y2 + 1] += k;}//还原数据for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){f[i][j] = f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1] + f[i][j];cout << f[i][j] << " ";}cout << endl;}return 0;
}
第一步：构建差分数组

第二步：修改差分数组

第三步：还原每个位置的数据并输出

【模板】二维差分

算法题（133）：二维差分

审题： 本题需要我们多次对某个矩形区域的数据加k，最后输出加完的数据思路： 方法一：二维差分本题涉及的是对二维的区间加同一个数的操作，且只显示一次最终结果，所以我们可以使用差分的方法二维差分的性质…...

编程日记 2025/7/5 9:33:42

java kafka

安装安装下载导入依赖 <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0"xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance"xsi:schemaLocation"http://maven.apach…...

编程日记 2025/6/29 11:41:17

数据结构【树和二叉树】

树和二叉树前言1.树1.1树的概念和结构1.2树的相关术语1.3树的表示方法1.4 树形结构实际运用场景 2.二叉树2.1二叉树的概念和结构2.2二叉树具备以下特点：2.3二叉树分类 3.满二叉树4.完全二叉树5.二叉树性质6.附：树和二叉树图示前言欢迎莅临姜行运主页…...

编程日记 2025/6/29 10:40:05

.NET代码保护混淆和软件许可系统——Eziriz .NET Reactor 7

.NET代码保护混淆和软件许可系统——Eziriz .NET Reactor 7 1、简介2、功能特点3、知识产权保护功能4、强大的许可系统5、软件开发工具包6、部署方式7、下载 1、简介 .NET Reactor是用于为.NET Framework编写的软件的功能强大的代码保护和软件许可系统，并且支持生成…...

编程日记 2025/6/29 12:28:36

运维打铁：Centos 7使用yum安装 Redis 5

文章目录一、安装前信息说明二、安装 Redis三、创建 Redis 相关数据目录四、启动 Redis 服务五、修改 Redis 数据目录和端口1. 修改 Redis 配置文件 /etc/redis.conf2. 拷贝数据到数据目录并授权3. 重启 Redis 并连接访问六、常见问题及解决办法1. Redis 安装失败2. Redis 服…...

编程日记 2025/7/5 8:28:57

【蓝桥杯】可分解的正整数

可分解的正整数定义一种特殊的整数序列，这种序列由连续递增的整数组成，并满足以下条件： 序列长度至少为 3。序列中的数字是连续递增的整数（即相邻元素之差为 1），可以包括正整数、负整数或 0。例如&…...

编程日记 2025/7/5 8:37:29

前言记录记录 1.LoginToMe int __fastcall main(int argc, const char **argv, const char **envp) {unsigned int v3; // eaxchar s[96]; // [rsp10h] [rbp-70h] BYREFint v6; // [rsp70h] [rbp-10h]int v7; // [rsp78h] [rbp-8h]int i; // [rsp7Ch] [rbp-4h]memset(s, 0, s…...

编程日记 2025/7/5 2:45:04

与终端同居日记：Shell交响曲の终极共舞指南

前言： 《与终端同居日记》特别篇：当文件们开始叠罗汉亲爱的压缩包驯兽师： 欢迎来到「文件马戏团」！在这里，zip是那个强迫症整理狂，tar是爱玩俄罗斯套娃的魔法师，而gzip——绝对是偷偷给文件喝…...

编程日记 2025/6/29 11:02:11

学习threejs，使用EffectComposer后期处理组合器（采用RenderPass、ShaderPass渲染通道），案例一

👨‍⚕️ 主页： gis分享者 👨‍⚕️ 感谢各位大佬点赞👍 收藏⭐ 留言📝 加关注✅! 👨‍⚕️ 收录于专栏：threejs gis工程师文章目录一、🍀前言1.1 ☘️THREE.EffectComposer 后期…...

编程日记 2025/6/29 10:18:31

【AI 加持下的 Python 编程实战 2_10】DIY 拓展：从扫雷小游戏开发再探问题分解与 AI 代码调试能力（中）

文章目录 DIY 实战：从扫雷小游戏开发再探问题分解能力3 问题分解实战（自顶向下）3.2 页面渲染逻辑3.3 事件绑定逻辑 4 代码实现（自底向上）4.1 页面渲染部分4.2 事件绑定部分写在前面本篇将利用《Learn AI-assisted Py…...

编程日记 2025/6/29 11:03:08

【数据可视化-27】全球网络安全威胁数据可视化分析（2015-2024）

🧑 博主简介：曾任某智慧城市类企业算法总监，目前在美国市场的物流公司从事高级算法工程师一职，深耕人工智能领域，精通python数据挖掘、可视化、机器学习等，发表过AI相关的专利并多次在AI类比赛中获奖。CSDN…...

编程日记 2025/7/2 22:29:53

Cephalon端脑云：神经形态计算+边缘AI·重定义云端算力

前引：当算力不再是“奢侈品” ，在人工智能、3D渲染、科学计算等领域，算力一直是横亘在个人与企业面前的“高墙”。高性能服务器价格动辄数十万元，专业设备维护成本高，普通人大多是望而却步。然而，Cephalon算…...

编程日记 2025/6/29 11:21:21

CSS简单实用的加载动画、骨架屏有效果图

效果图 .wxml  <view wx:for"{{skeleton}}" wx:key"index" class"container center" style"--w:{{item.w}}rpx;--h:{{item.h}}rpx" />  <view class"arco-loading center&quo…...

编程日记 2025/6/29 11:04:37

图论算法体系：并查集、生成树、排序与路径搜索全解析

从图论的基础理论入门，到深搜广搜搭建起图论的骨架。从并查集到最小生成树，从拓扑排序到最短路径。 .... 群星璀璨😉 并查集最小生成树 Prim算法Kruskal算法拓扑排序（kahn算法）最短路径 Dijkstra算法 Dijkstra朴素Di…...

编程日记 2025/6/29 11:28:15

OpenAI为何觊觎Chrome？AI时代浏览器争夺战背后的深层逻辑

目录引言：一场蓄谋已久的"蛇吞象"计划一、Chrome：数字世界的"黄金入口" 1.1 用户规模对比：ChatGPT与Chrome的悬殊差距 1.2 Chrome的生态价值远超浏览器本身二、OpenAI的"入口焦虑"与战略布局 2.1 AI时…...

编程日记 2025/7/5 7:50:26

DrissionPage 请求一次换一个代理（不重启chrome）

实现原理：通过插件实现 # !/usr/bin/python3 # -*- coding:utf-8 -*- """ author: JHC000abcgmail.com file: switch_ip.py time: 2025/4/23 22:05 desc:"""R""" 1. chrome s商店下载Proxy SwitchyOmega 3 (ZeroOme…...

编程日记 2025/6/29 10:56:11

JBoltAI 赋能金融文档：基于 RAG 的基金招募说明书视觉增强方案

在金融领域，基金招募说明书是投资者了解基金产品关键信息的重要文件。然而，这类文件通常以 PDF 格式呈现，内容繁杂、文本枯燥，对于普通投资者而言，理解起来存在一定难度。而如何利用 AI 技术对这类枯燥文本进行视觉增强…...

编程日记 2025/6/29 11:39:06

【玩转全栈】—— Django+vue3+讯飞星火API 实现前端页面实时AI答复

技术栈：vue3 element-plus axios pinia router Django5 websocket 讯飞星火API 本文将实现一个 AI 聊天对话功能，将前端用户输入问题以及之前对话发送给后端，通过 api 访问大模型，返回前端实时对话数据。调用讯飞星火API…...

编程日记 2025/6/29 9:23:11

1.1 java开发的准备工作（入门）

准备工作一.JDK 开始写java程序之前需要安装jdk jdk是java开发工具，包含着JRE和里面的JVM(虚拟机，可以使得不同环境下都能运行Java程序)，和开发工具。二.了解写程序的三大步骤步骤 java成功运行主要需要经过代码编写，编译&a…...

编程日记 2025/6/29 11:29:14

socket编程基础

上一篇 --- 网络基础概念（下）https://blog.csdn.net/Small_entreprene/article/details/147320155?fromshareblogdetail&sharetypeblogdetail&sharerId147320155&sharereferPC&sharesourceSmall_entreprene&sharefromfrom_link 理…...

编程日记 2025/6/29 9:47:38

根据定义给出json_schema:

根据您提供的智能体定义，以下是符合JSON Schema Draft-07规范的完整架构描述（包含中文注释说明）： {"$schema": ""title": "智能体架构规范","type": "object","req…...

编程日记 2025/6/29 10:52:13

深入微服务核心：从架构设计到规模化

作者：腾讯云开发者原文：深入微服务核心：从架构设计到规模化 01 微服务什么是微服务？ 微服务就是一些协同工作的小而自治的服务。我们在一个单体系统中，通常会采用一些抽象层或者模块来保证代码的内聚性&#xff0c…...

编程日记 2025/6/29 11:57:14

linux与c语言基础知识（未全部完成）

文章很多处理论，没办法写出来，（linux的一些理论问题，我有时间后，会逐个解决） 文章大多数的理论来字这个链接， C语言快速入门-C语言基础知识-CSDN博客一. linux（Ubuntu） …...

编程日记 2025/6/29 11:46:02

【专题刷题】滑动窗口（四）：

📝前言说明： 本专栏主要记录本人的基础算法学习以及LeetCode刷题记录，按专题划分每题主要记录：（1）本人解法本人屎山代码；（2）优质解法优质代码；&#xff…...

编程日记 2025/6/29 9:25:42

小白自学python第一天

学习python的第一天一、常用的值类型（先来粗略认识一下~） 类型说明数字（number）包含整型（int）、浮点型（float）、复数（complex）、布尔（boolean&…...

编程日记 2025/6/29 12:26:33

Redis 服务自动开启、设置密码和闪退问题

一、Redis 服务自动开启 1、以管理员身份运行命令提示符右键点击“命令提示符”图标，选择“以管理员身份运行”。 2、注册为 Windows 服务 redis-server --service-install 3、启动服务 redis-server --service-start 4、测试 Redis 连接 redis-cli ping …...

编程日记 2025/6/29 12:29:46

2025年渗透测试面试题总结-拷打题库14（题目+回答）

网络安全领域各种资源，学习文档，以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各种好玩的项目及好用的工具，欢迎关注。目录 2025年渗透测试面试题总结-拷打题库14 1. WAF存在的意义 2. 威胁感知能力衡量指标 3. 感知规则有效性…...

编程日记 2025/6/29 10:44:30

java后端开发day35--集合进阶（四）--双列集合：MapHashMapTreeMap

（以下内容全部来自上述课程） 1.双列集合 1.1 特点双列集合一次需要存一对数据，分别为键和值键不能重复，值可以重复键和值是一一对应的，每一个键只能找到自己对应的值键值这个整体，我们称之为“键值对”…...

编程日记 2025/6/29 9:23:33

进行网页开发时，怎样把function（）中变量值在控制台输出，查看?

在网页开发过程中，为了及时了解JavaScript中的function函数中的变量值，可以用控制台命令console.log()把变量的值在控制台输出，方便调试时对函数变量值进行了解。看下面的一段示例： <!DOCTYPE html> <html> &l…...

编程日记 2025/6/29 11:45:40

【计算机网络】现代网络技术核心架构与实战解析

目录前言技术背景与价值当前技术痛点解决方案概述目标读者说明一、技术原理剖析核心概念图解核心作用讲解关键技术模块说明技术选型对比二、实战演示环境配置要求核心代码实现案例1：TCP服务端/客户端通信案例2：Wireshark抓包分析三、性能对比测试方法…...

编程日记 2025/6/29 11:57:47

Python内置函数---bool()

用于将任意对象转换为布尔值（True或False） 1. 基本语法与参数 bool(x) - 参数：x为可选参数，可以是任意Python对象（如数值、字符串、列表、自定义对象等）。 - 返回值：根据x的真值性返回True或Fa…...

编程日记 2025/6/29 11:12:23

Vue 3中如何封装API请求：提升开发效率的最佳实践

在现代前端开发中，API请求是不可避免的一部分，尤其是与后端交互时。随着Vue 3的广泛应用，如何高效地封装API请求，既能提升代码的可维护性，又能确保代码的高复用性，成为了很多开发者关注的话题。在本文中&…...

编程日记 2025/6/29 11:43:50

【Redis】redis主从哨兵

Redis 主从复制在访问量极高的场景下，单台 Redis 已难以承载所有请求，且单点故障风险高。通过主从复制，可以实现读写分离、数据备份与高可用。概念主节点（Master）：负责写操作，将数据变更同…...

编程日记 2025/6/29 10:50:44

16.第二阶段x64游戏实战-分析二叉树结构

免责声明：内容仅供学习参考，请合法利用知识，禁止进行违法犯罪活动！ 本次游戏没法给内容参考于：微尘网络安全上一个内容：15.第二阶段x64游戏实战-分析怪物血量（遍历周围） 首先通…...

编程日记 2025/6/29 10:57:59

vue | 不同 vue 版本对复杂泛型的支持情况 · vue3.2 VS vue3.5

省流总结：defineProps 的泛型能力，来直接推导第三方组件的 props 类型引入第三方库的类型，并直接在 <script setup> 中作为 props 使用。这种类型一般是复杂泛型（包含联合类型、可选属性、交叉类型、条件类型等&#xff0…...

编程日记 2025/6/29 10:02:37

OpenGL学习笔记（Blinn-Phong、伽马矫正、阴影）

目录 Blinn-PhongGamma矫正GammaGamma矫正实现方法sRGB纹理衰减阴影shadow mapping渲染阴影改进阴影贴图PCF GitHub主页：https://github.com/sdpyy1 OpenGL学习仓库:https://github.com/sdpyy1/CppLearn/tree/main/OpenGLtree/main/OpenGL):https://github.com/sdp…...

编程日记 2025/7/4 5:48:21

GPLT-2025年第十届团体程序设计天梯赛总决赛题解(2025天梯赛题解,266分)

今天偶然发现天梯赛的代码还保存着，于是决定写下这篇题解，也算是复盘一下了 L1本来是打算写的稳妥点，最后在L1-6又想省时间，又忘记了insert，replace这些方法怎么用，也不想花时间写一个文件测试&#xff0c…...

编程日记 2025/6/29 10:29:13

day4 pandas学习

%pip install openxyxl 找一个自己觉得有意思的文件。我找的是成绩单来玩。这节学的比较耗时了，大概用了60分钟。 import pandas as pd data2 pd.read_csv(rD:\python代码区\代码随想录挑战-调试区\python训练营\1_计算类专业分流学生成绩排名.csv) #print(data)…...

编程日记 2025/6/29 10:03:12

【Java学习笔记】循环结构

循环结构一、for循环 for循环结构 for(循环变量初始化;循环条件;循环变量迭代){循环操作（可以多条语句） }for循环写死循环 for(;;){语句 }注意点：循环变量的初始化在for语句内，属于是局部变量，在全局中会出现未定义…...

编程日记 2025/6/29 9:23:21

URP-UGUI交互功能实现

一、非代码层面实现交互（SetActive） Button ：在OnClick（）中添加SetActive方法（但是此时只首次有效） Toggle ：在OnClick（）中添加动态的SetActive方法 &#…...

编程日记 2025/6/29 12:22:28

08-IDEA企业开发工具-集成AI插件通义灵码

需要登陆才可使用！！！ 1. 安装AI编程插件找到插件: 在IDEA的设置中，找到插件（Plugins）部分。安装插件: 搜索“通义灵码”，找到后点击安装（Install），接受条款…...

编程日记 2025/6/29 10:23:51

解决报错：this[kHandle] = new _Hash(algorithm, xofLen)；

前端项目编译报错： node:internal/crypto/hash:68this[kHandle] new _Hash(algorithm, xofLen);^Error: error:0308010C:digital envelope routines::unsupportedat new Hash (node:internal/crypto/hash:68:19)at Object.createHash (node:crypto:138:10)at modu…...

编程日记 2025/6/29 10:14:43

使用 Streamlit 打造一个简单的照片墙应用

在现代 web 开发中，快速构建交互式应用是一项重要的技能。Streamlit 是一个强大的 Python 库，允许开发者以最小的代码量创建美观且功能丰富的 web 应用。今天，我们将通过分析一段简单的 Streamlit 代码，展示如何构建一个照片墙应用…...

编程日记 2025/6/29 9:23:19

深度学习优化器和调度器的选择和推荐

一、常用优化器对比 1. 随机梯度下降（SGD） 原理：每次迭代使用小批量数据计算梯度并更新参数。优点：实现简单，适合大规模数据集。缺点：收敛速度慢，容易陷入局部最优或鞍点。适用场景&#xff1…...

编程日记 2025/6/29 11:39:14

“时间”，在数据处理中的真身——弼马温一般『无所不能』（DeepSeek）

电子表格时间处理真理：数值存储最瘦身，真身闯关通四海。笔记模板由python脚本于2025-04-23 22:25:59创建，本篇笔记适合喜欢在电子表格中探求时间格式的coder翻阅。【学习的细节是欢悦的历程】博客的核心价值：在于输出思考与经验…...

编程日记 2025/6/29 1:38:54

为什么Spring中@Bean注解默认创建单例Bean

在Spring框架中，使用Bean注解定义的对象默认确实是单例的，这是由Spring容器的设计哲学和实际需求决定的。下面我从多个角度解释这一设计选择的原因和机制。 1. Spring Bean作用域基础 Spring定义了多种Bean作用域，其中默认是单例(Singleton…...

编程日记 2025/6/29 12:20:43

GPLT-2025年第十届团体程序设计天梯赛总决赛题解(2025天梯赛题解，共计266分)

编程日记 2025/6/29 10:59:47

JDK（Ubuntu 18.04.6 LTS）安装笔记

一、前言本文与【MySQL 8（Ubuntu 18.04.6 LTS）安装笔记】同批次：先搭建数据库，再安装JDK，后面肯定就是部署Web应用：典型的单机部署。“麻雀虽小五脏俱全”，善始善终，还是记下来吧。…...

编程日记 2025/6/28 18:24:22

Java 拦截器完全指南：原理、实战与最佳实践

一、引言拦截器的基本概念在现代 Java Web 开发中，拦截器（Interceptor）是一种用于在请求处理前后插入自定义逻辑的机制。简单来说，它是一种“横切逻辑处理器”，可以用来对请求进行预处理、后处理，甚至终…...

编程日记 2025/6/29 11:58:19

2025.04.23华为机考第二题-200分

📌 点击直达笔试专栏 👉《大厂笔试突围》 💻 春秋招笔试突围在线OJ 👉 笔试突围OJ 02. 魔法彩灯森林问题描述在卢小姐的魔法花园中，有一棵神奇的彩灯树。这棵树的每个节点都装有一盏魔法灯，灯有三种颜色状态：红色（用数字1表示）、绿色（用数字2表示）和蓝色（…...

编程日记 2025/6/28 21:46:24

相关文章：