差分数组汇总

本文涉及知识点

算法与数据结构汇总

差分数组

令 a[i] = ∑ j : 0 i v D i f f [ i ] \sum_{j:0}^{i}vDiff[i] j:0ivDiff[i]
如果 vDiff[i1]++,则a[i1…]全部++
如果vDiff[i2]–,则a[i2…]全部–。
令11 < i2 ,则:
{ a [ i ] 不变,不受加减影响 i < i 1 a [ i ] 不变,加减抵消 i > = i 2 a [ i ] + + o t h e r \begin{cases} a[i]不变,不受加减影响 && i < i1 \\ a[i]不变,加减抵消 && i >= i2\\ a[i]++ && other \\ \end{cases} a[i]不变,不受加减影响a[i]不变,加减抵消a[i]++i<i1i>=i2other
即:a[i1…i2-1]++ ,其它不变。
区间更新、单点更新时间复杂度:O(1)。
区间查询、单点查询:O(n)
依次查询时间复杂度O(n),i从0到n-1查询a[i]的总时间复杂度是O(n)。
可与树状数组结合:更新查询全部是O(logn)
空间复杂度:O(n)

题解

难度分
【滑动窗口】【差分数组】C++算法:995K 连续位的最小翻转次数1835
【区间合并 差分数组】2963:统计好分割方案的数目1984
【差分数组】2772. 使数组中的所有元素都等于零2029
二分查找 差分数组LeetCode2251:花期内花的数目2022
【分解质因数 差分数组】2584. 分割数组使乘积互质2159
【差分数组】1674. 使数组互补的最少操作次数2333
【前缀和 二分查找 差分数组】2528最大化城市的最小供电站数目2235
【差分数组】【图论】【分类讨论】【整除以2】3017按距离统计房屋对数目2709
【上下界分析 差分数组】798得分最高的最小轮调

用map实现的差分

封装类

template<class KEY=int,class VALUE=int>
class CMapDiff
{
public:void Set(KEY left, KEY rExclue, VALUE value) {m_mDiff[left]+= value;m_mDiff[rExclue]-= value;}vector<pair<KEY, VALUE>> Ans()const {vector<pair<KEY, VALUE>> res;VALUE sum = 0;for (const auto& [key,value]: m_mDiff) {			sum += value;res.emplace_back(make_pair(key, sum));}return res;}
protected:map<KEY, VALUE> m_mDiff;
};

【区间合并 差分 栈】3169. 无需开会的工作日
大约2024年7月3号发

mDiff[si]++ mDiff[ei+1]-- 表示[si,ei] 一场会议。
∀ \forall mDiff的键 key,其下一个键为nkey。
∀ \forall k ∈ \in [key,nkey) mDiff[k]都为0,省略。
即:
x = ∑ i : 0 k e y m D i f f [ i ] = ∑ i : 0 k m D i f f [ i ] x = \sum_{i:0}^{key}mDiff[i] \quad = \sum_{i:0}^{k}mDiff[i] x=i:0keymDiff[i]=i:0kmDiff[i]
如果x不为0,则[key,nkey)全部要开会。

二维差分

a[i][j] = ∑ i 1 : 0 i ∑ j 1 : 0 j v D i f f [ i ] [ j ] \sum_{i1:0}^i \sum_{j1:0}^jvDiff[i][j] i1:0ij1:0jvDiff[i][j]
a[i1…i2][j1…j2] ++的操作:
vDiff[i1][j1]++ vDiff[i2+1][j2+1]++
vDiif[i1][j2+1]-- vDiff[2+1][j1]–
注意:差分都是左闭右开空间
求前缀和的简单方法:
vCol[j] = ∑ i 1 : 0 i v D i i f [ i 1 ] [ j ] \sum_{i1:0}^{i}vDiif[i1][j] i1:0ivDiif[i1][j]
a[i][j] = ∑ j 1 : 0 j v C o l [ j 1 ] \sum_{j1:0}^j vCol[j1] j1:0jvCol[j1]

封装类

template<class T = int >
class CDiff2
{
public:CDiff2(int r, int c):m_iR(r),m_iC(c) {m_vDiff.assign(m_iR, vector<T>(m_iC));}void Set(int r1, int c1, int r2Exinc, int c2Exinc,int iAdd) {m_vDiff[r1][c1] += iAdd;m_vDiff[r2Exinc][c2Exinc] += iAdd;m_vDiff[r1][c2Exinc] -= iAdd;m_vDiff[r2Exinc][c1] -= iAdd;}vector<vector<T>> Ans()const {vector<vector<T>> res(m_iR, vector<T>(m_iC));vector<T> vCols(m_iC);for (int r = 0; r < m_iR; r++) {T iSum = 0;for (int c = 0; c < m_iC; c++) {vCols[c] += m_vDiff[r][c];iSum += vCols[c];res[r][c] = iSum;}}return res;}const int m_iR, m_iC;
protected:vector<vector<T>> m_vDiff;
};

题解

难度分
【离散化 二维差分】850. 矩形面积 II2335
【二维差分】2132. 用邮票贴满网格图2364
【离散化 二维差分】391. 完美矩形

扩展阅读

视频课程

先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关推荐

我想对大家说的话
《喜缺全书算法册》以原理、正确性证明、总结为主。
按类别查阅鄙人的算法文章,请点击《算法与数据汇总》。
有效学习:明确的目标 及时的反馈 拉伸区(难度合适) 专注
闻缺陷则喜(喜缺)是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙,那算法就是他的是睛

测试环境

操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。

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

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

相关文章

码住!详解时序数据库不同分类与性能对比

加速发展中的时序数据库&#xff0c;基于不同架构&#xff0c;最流行的类别是&#xff1f; 作为管理工业场景时序数据的新兴数据库品类&#xff0c;时序数据库凭借着对海量时序数据的高效存储、高可扩展性、时序分析计算等特性&#xff0c;一跃成为物联网时代工业领域颇受欢迎的…

RK3568技术笔记十二 Android编译方法

Android源码说明 Android源码在SAIL-RK3568开发板光盘->Android->源代码中&#xff0c;由于android源码太大&#xff0c;在进行压缩时&#xff0c;进行分包压缩&#xff0c;因此有4部分&#xff0c;如图所示&#xff1a; 进行解压时&#xff0c;需将4部分压缩包放置同一…

技术差异,应用场景;虚拟机可以当作云服务器吗

虚拟机和云服务器是现在市面上常见的两种计算资源提供方式&#xff0c;很多人把这两者看成可以相互转换或者替代的物品&#xff0c;实则不然&#xff0c;这两种资源提供方式有许多相似之处&#xff0c;但是也有不少区别&#xff0c;一篇文章教你识别两者的技术差异&#xff0c;…

快速搭建Jenkins自动化集成cicd工具

一、简介 jenkins是一款优秀的自动化持续集成运维工具&#xff0c;可以极大的简化运维部署的步骤。 传统的项目部署需要手动更换最新的项目代码&#xff0c;然后打包并运行到服务器上。 使用Jenkins可以自动化实现&#xff0c;当代码编写完成并提交到git后&#xff0c;Jenki…

【前端项目笔记】3 用户管理

用户管理相关功能实现 涉及表单、对话框、Ajax数据请求 基本页面 用户列表开发 在router.js中导入Users.vue 解决用户列表小问题 选中&#xff08;激活&#xff09;子菜单后刷新不显示高亮 给二级菜单绑定单击事件&#xff0c;点击链接时把对应的地址保存到sessionSto…

使用高德API计算两个地址的距离

要使用高德地图API来计算两个城市之间的距离&#xff0c;你需要首先在高德开放平台上注册并获取API密钥&#xff08;AK&#xff09;。以下是一个使用Java调用高德地图API来计算两个城市之间距离的示例代码。 步骤 1: 获取高德地图API密钥 访问高德开放平台&#xff08;https:…

FreeRTOS源码分析

目录 1、FreeRTOS目录结构 2、核心文件 3、移植时涉及的文件 4、头文件相关 4.1 头文件目录 4.2 头文件 5、内存管理 6、入口函数 7、数据类型和编程规范 7.1 数据类型 7.2 变量名 7.3 函数名 7.4 宏的名 1、FreeRTOS目录结构 使用 STM32CubeMX 创建的 FreeRTOS 工…

【odoo | JSON-RPC】无会话(session_id)控制的api,外部api密钥的另一种表现!

概要 在Odoo中&#xff0c;JSON-RPC&#xff08;JSON Remote Procedure Call&#xff09;是一种基于JSON格式的远程过程调用协议&#xff0c;用于客户端和服务器之间的通信。此文章将介绍 JSON-RPC中无会话(session_id)控制的api&#xff0c;也是外部api密钥的另一种表现方式。…

百度文心智能体平台(想象即现实):轻松上手,开启智能新时代!创建属于自己的智能体应用。

目录 1.1、文心智能体平台 1.2、创建智能体 1.3、智能体报名入口 1.4、古诗词小助手 1.5、访问我的智能体 在这个全新的时代里&#xff0c;人工智能技术正以前所未有的速度发展&#xff0c;渗透到我们生活的方方面面。无论是智能家居、自动驾驶&#xff0c;还是医疗诊断、…

深入探讨:UART与USART在单片机中串口的实际应用与实现技巧

单片机&#xff08;Microcontroller Unit, MCU&#xff09;是一种集成了处理器、存储器和输入输出接口的微型计算机。它广泛应用于嵌入式系统中&#xff0c;用于控制各类电子设备。UART和USART是单片机中常见的通信接口&#xff0c;负责串行数据传输。下面我们详细介绍它们在单…

【LeetCode:394. 字符串解码 + 栈 | 递归】

&#x1f680; 算法题 &#x1f680; &#x1f332; 算法刷题专栏 | 面试必备算法 | 面试高频算法 &#x1f340; &#x1f332; 越难的东西,越要努力坚持&#xff0c;因为它具有很高的价值&#xff0c;算法就是这样✨ &#x1f332; 作者简介&#xff1a;硕风和炜&#xff0c;…

Sqlite3数据库基本使用

一、基本概念 数据&#xff1a;能够输入计算机并能被计算机程序识别和处理的信息集合 数据库&#xff1a;长期存储在计算机内、有组织的、可共享的大量数据的集合 DBMS&#xff1a;位于用户与操作系统之间的一层数据管理软件&#xff0c;用于操纵和管理数据库 二、安装 在线…

智能合约新项目 链上智能合约前端H5源码 智能合约区块链 以太坊前端调用智能合约

智能合约新项目 链上智能合约前端H5源码 智能合约区块链 以太坊前端调用智能合约 源码下载&#xff1a;https://download.csdn.net/download/m0_66047725/89402192 更多资源下载&#xff1a;关注我。

【OceanBase诊断调优】 —— DDL时报磁盘不足问题排查

1. 背景 由于在4.x的部分版本中&#xff0c;我们对于一些ddl操作还存在磁盘空间放大问题&#xff0c;本文主要介绍了这一类问题的排查。 2. 问题排查 2.1 整体排查链路 2.2 问题现象 DDL过程中报磁盘空间不足&#xff0c;需要确认是否符合预期&#xff0c;如果是符合预期&a…

1980python个性化电影推荐管理系统mysql数据库Django结构layUI布局elasticsearch存储计算机软件工程网页

一、源码特点 python Django个性化电影推荐管理系统是一套完善的web设计系统mysql数据库 利用elasticsearch存储浏览数据 &#xff0c;对理解python编程开发语言有帮助&#xff0c;系统具有完整的源代码和数据库&#xff0c;系统主要采用B/S模式开发。 开发环境pycharm…

基于STM32的智能水产养殖系统(四)

硬件原理 步进电动机 步进电动机&#xff08;Step Motor 或 Stepper Motor&#xff09;是一种将电脉冲信号转换成对应的角位移或线位移的电动机。与普通电动机不同&#xff0c;步进电动机每接收到一个脉冲信号&#xff0c;就会按设定的角度&#xff08;步距角&#xff09;转动…

定制汽车霍尔传感器

磁电效应霍尔传感器、饱和霍尔传感器、非线性霍尔传感器 霍尔传感器原理 霍尔传感器的工作原理基于霍尔效应&#xff0c;即当一块通有电流的金属或半导体薄片垂直地放在磁场中时&#xff0c;薄片的两端会产生电位差。这种现象称为霍尔效应&#xff0c;两端具有的电位差值称为…

STM32通过I2C软件读写MPU6050

文章目录​​​​​​​ 1. MPU6050 1.1 运动学概念 1.2 工作原理 2. 参数 2.1 量程选择 2.2 I2C从机地址配置 3. 硬件电路 4. 框架图 5. 软件和硬件波形对比 6. 软件I2C读写MPU6050 6.1 程序整体构架 6.2 一些需要注意的点&#xff1a; 6.3 MPU6050初始化配置 6…

【Python/Pytorch 】-- 滑动窗口算法

文章目录 文章目录 00 写在前面01 基于Python版本的滑动窗口代码02 算法效果 00 写在前面 写这个算法原因是&#xff1a;训练了一个时序网络&#xff0c;该网络模型的时序维度为32&#xff0c;而测试数据的时序维度为90。因此需要采用滑动窗口的方法&#xff0c;生成一系列32…

第58章SOCKET:TCP/IP网络基础

58.1 互联网 互联网会将不同的计算机网络连接起来并允许位于网络中的主机相互之间进行通信。互联网的目标是隐藏不同物理网络的细节以便向互联网中的所有主机呈现一个统一的网络架构&#xff0c;TCP/IP已经成了使用最为广泛的协议套件了&#xff0c; 术语Internet被用来指将全球…