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

二维差分---三维差分算法笔记

在这里插入图片描述

文章目录

  • 一.二维差分
    • 构造差分二维数组
    • 二维差分算法
    • 状态dp求b[i][j]数组的二维前缀和图解
  • 二.三维前缀和与差分
    • 三维前缀和图解:
    • 三维差分核心公式图解:
    • 模板题

一.二维差分

  • 给定一个原二维数组a[i][j],若要给a[i][j]中以(x1,y1)(x2,y2)为对角线的子矩阵中每个数都加上一个常数c,暴力的做法时间复杂度为O(N^2),使用二维差分可以在O(1)的时间复杂度内完成该操作
    在这里插入图片描述

构造差分二维数组

  • 构造差分二维数组b[i][j]使得原二维数组a[i][j]是二维数组b[i][j]的二维前缀和数组,即满足:
    在这里插入图片描述
    在这里插入图片描述

二维差分算法

  • 若使原数组a[i][j]中以(x1,y1)(x2,y2)为对角线的子矩阵中每个数都加上一个常数c,等价于对b[i][j]数组进行如下操作:
    • b[x1][y1] += c
    • b[x2+1][y2+1] += c
    • b[x2+1][y1] -= c
    • b[x1][y2+1] -= c
  • 核心操作接口:
//使原数组a[i][j]中以(x1,y1)和(x2,y2)为对角线的子矩阵中每个数都加上一个常数c
//接口可以用于构造差分矩阵以及进行原数组的矩阵元素整体修改操作
void Matrix_Add(long long(*b)[1010],int x1 ,int y1,int x2 ,int y2,int c){b[x1][y1] += c;b[x2+1][y2+1] += c;b[x1][y2+1] -= c;b[x2+1][y1] -= c;
}
//状态递推法对b[i][j]数组求二维前缀和,以获取原数组的元素--> 默认矩阵第0行第0列全部元素为0
void Get_Pre_Sum(long long(*b)[1010],int row , int col){//求(1,1)~(i,j)的子矩阵的和for(int i = 1 ; i <= row ; ++i){for(int j = 1 ; j<=col ; ++j){b[i][j] += (b[i-1][j] + b[i][j-1] - b[i-1][j-1]);}}
}
  • 求出b[i][j]数组的二维前缀和就可以恢复原数组a[i][j]

状态dp求b[i][j]数组的二维前缀和图解

在这里插入图片描述

二.三维前缀和与差分

三维前缀和图解:

在这里插入图片描述

  • 前缀和递推构造接口:
void Get_Pre_Sum(vector<vector<vector<long long>>>& Board,int high,int row,int col ){for(int i = 1 ; i <= high ; ++i){for(int j = 1 ;  j <= row ; ++j){for(int k = 1 ; k <= col ; ++k){Board[i][j][k] += Board[i-1][j][k] + Board[i][j-1][k] - Board[i-1][j-1][k] +Board[i][j][k-1] - Board[i-1][j][k-1] - Board[i][j-1][k-1] + Board[i-1][j-1][k-1];}}}
}

三维差分核心公式图解:

在这里插入图片描述

  • "相邻点"的加减满足容斥关系,相邻互斥,相间相容
  • 核心公式接口:
void Matrix_Add(vector<vector<vector<long long>>>& Board,int x1 , int y1 , int z1 , int x2 , int y2 , int z2 , int c){Board[x1][y1][z1] += c;Board[x1][y2+1][z1] -= c;Board[x2+1][y1][z1] -= c;Board[x2+1][y2+1][z1] += c;Board[x1][y1][z2+1] -= c;Board[x1][y2+1][z2+1] += c;Board[x2+1][y1][z2+1] += c;Board[x2+1][y2+1][z2+1] -= c;
}

模板题

差分模板题1
差分模板题2

在这里插入图片描述

相关文章:

二维差分---三维差分算法笔记

文章目录 一.二维差分构造差分二维数组二维差分算法状态dp求b[i][j]数组的二维前缀和图解 二.三维前缀和与差分三维前缀和图解:三维差分核心公式图解:模板题 一.二维差分 给定一个原二维数组a[i][j],若要给a[i][j]中以(x1,y1)和(x2,y2)为对角线的子矩阵中每个数都加上一个常数…...

D. Divisible Pairs

思路&#xff1a;我们预处理出每个数分别摸上xy的值&#xff0c;用map存一下&#xff0c;然后遍历每个数&#xff0c;如果a b是x的倍数的话&#xff0c;那么他们模x的值相加为x&#xff0c;如果a - b是y的倍数的话&#xff0c;那么他们的模y的值相等。 代码&#xff1a; voi…...

【教程】Kotlin语言学习笔记(二)——数据类型(持续更新)

写在前面&#xff1a; 如果文章对你有帮助&#xff0c;记得点赞关注加收藏一波&#xff0c;利于以后需要的时候复习&#xff0c;多谢支持&#xff01; 【Kotlin语言学习】系列文章 第一章 《认识Kotlin》 第二章 《数据类型》 文章目录 【Kotlin语言学习】系列文章一、基本数据…...

react 插槽

问题开发当中会经常出现组件十分相似的组件&#xff0c;只有一部分是不同的 解决&#xff1a; 父组件:在引用的时候 import { Component } from "react"; import Me from "../me";const name <div>名称</div> class Shoop extends Compone…...

Linux运用fork函数创建进程

fork函数&#xff1a; 函数原型&#xff1a; pid_t fork(void); 父进程调用fork函数创建一个子进程&#xff0c;子进程的用户区父进程的用户区完全一样&#xff0c;但是内核区不完全一样&#xff1b;如父进程的PID和子进程的PID不一样。 返回值&#xff1a; RETURN VALUEO…...

Pytest测试技巧之Fixture:模块化管理测试数据

在 Pytest 测试中&#xff0c;有效管理测试数据是提高测试质量和可维护性的关键。本文将深入探讨 Pytest 中的 Fixture&#xff0c;特别是如何利用 Fixture 实现测试数据的模块化管理&#xff0c;以提高测试用例的清晰度和可复用性。 什么是Fixture&#xff1f; 在 Pytest 中&a…...

设计模式-职责链模式Chain of Responsibility

职责链模式 一、原理和实现二、实现方式1) 使用链表实现2) 使用数组实现3) 扩展 作用&#xff1a;复用和扩展&#xff0c;在实际的项目开发中比较常用。在框架开发中&#xff0c;我们也可以利用它们来提供框架的扩展点&#xff0c;能够让框架的使用者在不修改框架源码的情况下&…...

书生浦语大模型实战营-课程作业(3)

下载sentence_transformer的代码运行情况。sentence_transformer用于embedding&#xff08;转向量&#xff09; 本地构建持久化向量数据库。就是把txt和md文件抽取出纯文本&#xff0c;分割成定长&#xff08;500&#xff09;后转换成向量&#xff0c;保存到本地&#xff0c;称…...

考研英语单词25

Day 25 bench n.长凳 elastic n.橡皮圈&#xff0c;松紧带 a.灵活的 “e-last 延伸出去” disaster n.灾难&#xff0c;灾祸【disastrous a.灾难性的&#xff0c;极坏的】 deadly a.致命的&#xff0c;极端的&#xff0c;势不两立的 hike n.徒步旅行&…...

计算机网络——08应用层原理

应用层原理 创建一个新的网络 编程 在不同的端系统上运行通过网络基础设施提供的服务&#xff0c;应用进程批次通信如Web Web服务器软件与浏览器软件通信 网络核心中没有应用层软件 网络核心没有应用层功能网络应用只能在端系统上存在 快速网络应用开发和部署 网络应用…...

面试计算机网络框架八股文十问十答第五期

面试计算机网络框架八股文十问十答第五期 作者&#xff1a;程序员小白条&#xff0c;个人博客 相信看了本文后&#xff0c;对你的面试是有一定帮助的&#xff01;关注专栏后就能收到持续更新&#xff01; ⭐点赞⭐收藏⭐不迷路&#xff01;⭐ 1&#xff09;与缓存相关的HTTP请…...

拟合案例1:matlab积分函数拟合详细步骤及源码

本文介绍一下基于matlab实现积分函数拟合的过程。采用的工具是lsqcurvefit和nlinfit两个函数工具。关于包含积分运算的函数,这里可以分为两大类啊。我们用具体的案例来展示:一种是积分运算中不包含这个自变量,如下图的第一个公式,也就是说它这个积分运算只有R和Q这两个待定…...

嵌入式软件设计入门:从零开始学习嵌入式软件设计

&#xff08;本文为简单介绍&#xff0c;个人观点仅供参考&#xff09; 首先,让我们了解一下嵌入式软件的定义。嵌入式软件是指运行在嵌入式系统中的特定用途软件,它通常被用来控制硬件设备、处理实时数据和实现特定功能。与桌面应用程序相比,嵌入式软件需要具备更高的实时性、…...

Educational Codeforces Round 135 (Rated for Div. 2)C. Digital Logarithm(思维)

文章目录 题目链接题意题解代码 题目链接 C. Digital Logarithm 题意 给两个长度位 n n n的数组 a a a、 b b b&#xff0c;一个操作 f f f 定义操作 f f f为&#xff0c; a [ i ] f ( a [ i ] ) a [ i ] a[i]f(a[i])a[i] a[i]f(a[i])a[i]的位数 求最少多少次操作可以使 …...

微信小程序介绍、账号申请、开发者工具目录结构详解及小程序配置

目录 一、微信小程序介绍 1.什么是小程序&#xff1f; 2.小程序可以干什么&#xff1f; 3.微信小程序特点 二、账号申请 1.账号注册 2.测试号申请 三、安装开发工具 四、开发小程序 五、目录结构 JSON 配置 小程序配置 app.json 工具配置 project.config.json 页…...

数字的魅力之情有独钟的素数

情有独钟的素数 什么是素数 素数&#xff08;Prime number&#xff09;也称为质数&#xff0c;是指在非0自然数中&#xff0c;除了1与其本身之外不拥有其他因数的自然数。也就是说&#xff0c;素数需要满足两个条件&#xff1a; 大于1的整数&#xff1b;只拥有1和其自身两个…...

Vue2源码梳理:render函数的实现

render 在 $mount 时&#xff0c;会调用 render 方法在写 template 时&#xff0c;最终也会转换成 render 方法Vue 的 _render 方法是实例的一个私有方法&#xff0c;它用来把实例渲染成一个虚拟 Node它的定义在 src/core/instance/render.js 文件中&#xff0c;它返回的是一个…...

flask+python企业产品订单管理系统938re

在设计中采用“自下而上”的思想&#xff0c;在创新型产品提前购模块实现了个人中心、个体管理、发布企业管理、投资企业管理、项目分类管理、产品项目管理、个体投资管理、企业投资管理、个体订单管理、企业订单管理、系统管理等的功能性进行操作。最终&#xff0c;对基本系统…...

Vue2源码梳理:关于数据驱动,与new Vue时的初始化操作

数据驱动 1 &#xff09;概述 vue的一个核心思想&#xff0c;就是数据驱动 所谓数据驱动&#xff0c;就是指视图是由数据驱动生成的 对视图的修改并不会直接操作dom&#xff0c;而是通过修改数据 它相比我们传统的前端开发&#xff0c;如使用 jQuery 的前端库直接去修改 dom…...

【C++航海王:追寻罗杰的编程之路】关于模板,你知道哪些?

目录 1 -> 泛型编程 2 -> 函数模板 2.1 -> 函数模板概念 2.2 -> 函数模板格式 2.3 -> 函数模板的原理 2.4 -> 函数模板的实例化 2.5 -> 函数参数的匹配原则 3 -> 类模板 3.1 -> 类模板的定义格式 3.2 -> 类模板的实例化 1 -> 泛型编…...

盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来

一、破局&#xff1a;PCB行业的时代之问 在数字经济蓬勃发展的浪潮中&#xff0c;PCB&#xff08;印制电路板&#xff09;作为 “电子产品之母”&#xff0c;其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透&#xff0c;PCB行业面临着前所未有的挑战与机遇。产品迭代…...

【Linux】C语言执行shell指令

在C语言中执行Shell指令 在C语言中&#xff0c;有几种方法可以执行Shell指令&#xff1a; 1. 使用system()函数 这是最简单的方法&#xff0c;包含在stdlib.h头文件中&#xff1a; #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...

C# 表达式和运算符(求值顺序)

求值顺序 表达式可以由许多嵌套的子表达式构成。子表达式的求值顺序可以使表达式的最终值发生 变化。 例如&#xff0c;已知表达式3*52&#xff0c;依照子表达式的求值顺序&#xff0c;有两种可能的结果&#xff0c;如图9-3所示。 如果乘法先执行&#xff0c;结果是17。如果5…...

LCTF液晶可调谐滤波器在多光谱相机捕捉无人机目标检测中的作用

中达瑞和自2005年成立以来&#xff0c;一直在光谱成像领域深度钻研和发展&#xff0c;始终致力于研发高性能、高可靠性的光谱成像相机&#xff0c;为科研院校提供更优的产品和服务。在《低空背景下无人机目标的光谱特征研究及目标检测应用》这篇论文中提到中达瑞和 LCTF 作为多…...

前端开发者常用网站

Can I use网站&#xff1a;一个查询网页技术兼容性的网站 一个查询网页技术兼容性的网站Can I use&#xff1a;Can I use... Support tables for HTML5, CSS3, etc (查询浏览器对HTML5的支持情况) 权威网站&#xff1a;MDN JavaScript权威网站&#xff1a;JavaScript | MDN...

如何在Windows本机安装Python并确保与Python.NET兼容

✅作者简介&#xff1a;2022年博客新星 第八。热爱国学的Java后端开发者&#xff0c;修心和技术同步精进。 &#x1f34e;个人主页&#xff1a;Java Fans的博客 &#x1f34a;个人信条&#xff1a;不迁怒&#xff0c;不贰过。小知识&#xff0c;大智慧。 &#x1f49e;当前专栏…...

结构化文件管理实战:实现目录自动创建与归类

手动操作容易因疲劳或疏忽导致命名错误、路径混乱等问题&#xff0c;进而引发后续程序异常。使用工具进行标准化操作&#xff0c;能有效降低出错概率。 需要快速整理大量文件的技术用户而言&#xff0c;这款工具提供了一种轻便高效的解决方案。程序体积仅有 156KB&#xff0c;…...

Java多线程实现之Runnable接口深度解析

Java多线程实现之Runnable接口深度解析 一、Runnable接口概述1.1 接口定义1.2 与Thread类的关系1.3 使用Runnable接口的优势 二、Runnable接口的基本实现方式2.1 传统方式实现Runnable接口2.2 使用匿名内部类实现Runnable接口2.3 使用Lambda表达式实现Runnable接口 三、Runnabl…...

WEB3全栈开发——面试专业技能点P8DevOps / 区块链部署

一、Hardhat / Foundry 进行合约部署 概念介绍 Hardhat 和 Foundry 都是以太坊智能合约开发的工具套件&#xff0c;支持合约的编译、测试和部署。 它们允许开发者在本地或测试网络快速开发智能合约&#xff0c;并部署到链上&#xff08;测试网或主网&#xff09;。 部署过程…...

RocketMQ 客户端负载均衡机制详解及最佳实践

延伸阅读&#xff1a;&#x1f50d;「RocketMQ 中文社区」 持续更新源码解析/最佳实践&#xff0c;提供 RocketMQ 专家 AI 答疑服务 前言 本文介绍 RocketMQ 负载均衡机制&#xff0c;主要涉及负载均衡发生的时机、客户端负载均衡对消费的影响&#xff08;消息堆积/消费毛刺等…...