差分数组汇总
本文涉及知识点
算法与数据结构汇总
差分数组
令 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:0i∑j1: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. 矩形面积 II | 2335 |
【二维差分】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++**实现。
相关文章:

差分数组汇总
本文涉及知识点 算法与数据结构汇总 差分数组 令 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 ] 不变&…...

SpringBoot | 实现邮件发送
运行环境: IntelliJ IDEA 2022.2.5 (Ultimate Edition) (注意:idea必须在2021版本以上)JDK17 项目目录: 该项目分为pojo,service,controller,utils四个部分, 在pojo层里面写实体内容(发邮件需要的发件人邮…...

spring boot接入nacos 配置中心
再接入nacos配置中心时,需要确认几点: 1. spring boot 版本 (spring boot 2.x ) 2. nacos 配置中心 服务端 版本 (1.1.4) 3. nacos client 客户端版本 (1.1.4) 方式一 1. 启动 nacos 服务端,这里不做解释 在配置中心中加入几个配置 2. 在…...

产品应用 | 小盒子跑大模型!英码科技基于算能BM1684X平台实现大模型私有化部署
当前,在人工智能领域,大模型在丰富人工智能应用场景中扮演着重要的角色,经过不断的探索,大模型进入到落地的阶段。而大模型在落地过程中面临两大关键难题:对庞大计算资源的需求和对数据隐私与安全的考量。为应对这些挑…...

uniapp中u-input点击事件失效
当给u-input设置了disabled/readonly属性后,pc浏览器中点击事件失效,但是app/移动端h5中却仍有效 解决办法 给外边包上一个盒子设置点击事件,给input加上css属性:pointer-events:none pointer-events CSS 属性指定在什…...
[机器学习] 监督学习和无监督学习
监督学习和无监督学习是机器学习的两种主要方法,它们之间有几个关键区别: 1. 定义 监督学习(Supervised Learning): 使用带标签的数据进行训练。数据集包括输入特征和对应的输出标签。目标是学习从输入特征到输出标签…...
使用Python进行自然语言处理:从基础到实战
使用Python进行自然语言处理:从基础到实战 自然语言处理(Natural Language Processing, NLP)是人工智能的重要领域,旨在处理和分析自然语言数据。Python凭借其丰富的库和社区支持,成为NLP的首选编程语言。本文将介绍自然语言处理的基础概念、常用的Python库以及一个实战项…...
Hadoop面试题总结
一 、介绍一下hadoop 综述:hadoop是一个适合海量数据的分布式存储和分布式计算的平台 分述:hadoop包含三大组件,分别是HDFS、MapReduce和YARN --HDFS(分布式文件系统) HDFS集群由NameNode,DataNode,SecondaryNameNode构成NameNode:主要负责接受用户请求…...

关于IntelliJ IDEA 2024.1版本更新的问题
希望文章能给到你启发和灵感~ 感谢支持和关注~ 阅读指南 序幕一、基础环境说明1.1 硬件环境1.2 软件环境 二、起因三、解决四、总结 序幕 近期,IntelliJ IDEA 推出了全新2024版本,相信很多编程的爱好者或者刚接触编程的小伙伴都会…...

双层循环和循环语句
echo 打印 echo -n 表示不换行输出 echo -e 表示输出转义字符 echo \b 相当于退格键(backspace) echo \n 换行,相当于回车 echo \f 换行,换行后的新行的开头连着上一行的行尾 echo \t 相当于tab健 (…...

【Codesys】-计算开机通电运行时间,累计正常使用时间,故障停机时间
应客户要求,在程序添加了这个用来计算开机运行时间,原理就是取当前时间减去一开始记录的时间,没什么特别要求,记录一下使用的变量类型和数据写法,防止忘记了。 下文只写了一个开机通电运行时间的写法,累计…...

LINUX系统编程:线程的概念
目录 1.线程的概念 2.线程的理解 3.怎么做到划分代码的 本文主要介绍,在LIUNX下的线程。 1.线程的概念 在很多的书上的你可能见过这样的。 线程是进程内部的一个执行分支,线程是cpu调度的基本单位。 加载到内存的程序叫做进程。修正:进…...

如何更换OpenHarmony SDK API 10
OpenHarmony社区已经发布OpenHarmony SDK API 10 beta版本,有些 Sample案例 也有需要API10。那么如何替换使用新的OpenHarmony SDK API 10呢?本文做个记录。 1、如何获取OpenHarmony SDK 1.1 每日构建流水线 可以从OpenHarmony每日构建站点获取最新的…...

Java | Leetcode Java题解之第155题最小栈
题目: 题解: class MinStack {Deque<Integer> xStack;Deque<Integer> minStack;public MinStack() {xStack new LinkedList<Integer>();minStack new LinkedList<Integer>();minStack.push(Integer.MAX_VALUE);}public void …...

大润发超市购物卡怎么用?
收到大润发超市的礼品卡以后,我才发现,最近的大润发也得十来公里 为了100块的大润发打车也太不划算了 叫外送也不在配送范围内 最后没办法,在收卡云上出掉了,还好最近价格不错,也不亏,收卡云的到账速度也…...

【ai】tx2-nx:搭配torch的torchvision
微雪的教程pytorch_version 1.10.0 官方教程安装torch官方教程 依赖项 nvidia@tx2-nx:~/twork/03_yolov5$ $ sudo apt-get install libjpeg-dev zlib1g-dev lib...
深入浅出MyBatis:全面解析与实战指南
MyBatis 是一个优秀的持久层框架,它简化了 Java 应用与关系数据库之间的映射。对于大多数 Java 开发者而言,掌握 MyBatis 是必不可少的一部分。本文将详细介绍 MyBatis 的各个方面,包括其基本原理、配置、操作、动态 SQL、插件机制和高级应用…...

好用的linux一键换源脚本
最近发现一个好用的linux一键换源脚本,记录一下 官方链接 大陆使用 bash <(curl -sSL https://linuxmirrors.cn/main.sh)# github地址 bash <(curl -sSL https://raw.githubusercontent.com/SuperManito/LinuxMirrors/main/ChangeMirrors.sh) # gitee地址 …...
机器人----控制方式
位置控制 点位控制 点到点--PTP 只关心起点和目标点,不关心走过的轨迹。 连续轨迹控制 CP(continus path) eg:焊接,切割。 力控制 使用多大的力进行控制。 eg:用多大的力写字。...
json的特点
JJSON是一种轻量级的数据交换格式,它基于JavaScript编程语言的一个子集,采用完全独立于语言的文本格式,结构化程度高。 JSON的主要特点包括: 轻量级:JSON的格式紧凑,易于传输和解析。 结构化:…...

Linux 文件类型,目录与路径,文件与目录管理
文件类型 后面的字符表示文件类型标志 普通文件:-(纯文本文件,二进制文件,数据格式文件) 如文本文件、图片、程序文件等。 目录文件:d(directory) 用来存放其他文件或子目录。 设备…...
PHP和Node.js哪个更爽?
先说结论,rust完胜。 php:laravel,swoole,webman,最开始在苏宁的时候写了几年php,当时觉得php真的是世界上最好的语言,因为当初活在舒适圈里,不愿意跳出来,就好比当初活在…...

JavaScript 中的 ES|QL:利用 Apache Arrow 工具
作者:来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗?了解下一期 Elasticsearch Engineer 培训的时间吧! Elasticsearch 拥有众多新功能,助你为自己…...
postgresql|数据库|只读用户的创建和删除(备忘)
CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...
Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器
第一章 引言:语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域,文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量,支撑着搜索引擎、推荐系统、…...
在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用
1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...
【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分
一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计,提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合:各模块职责清晰,便于独立开发…...

mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包
文章目录 现象:mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时,可能是因为以下几个原因:1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...
AspectJ 在 Android 中的完整使用指南
一、环境配置(Gradle 7.0 适配) 1. 项目级 build.gradle // 注意:沪江插件已停更,推荐官方兼容方案 buildscript {dependencies {classpath org.aspectj:aspectjtools:1.9.9.1 // AspectJ 工具} } 2. 模块级 build.gradle plu…...
大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计
随着大语言模型(LLM)参数规模的增长,推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长,而KV缓存的内存消耗可能高达数十GB(例如Llama2-7B处理100K token时需50GB内存&a…...