程序员经验分享-hwhale

9.28

2023-05-16

昨天的大概就咕咕咕了

今天说差分

多图预警

于是,进入正题

今天的主题是差分

但我们或许也应该先说说前缀和

众所周知,差分是前缀和的逆运算

跟我一起念三遍:

　　差分是前缀和的逆运算,差分是前缀和的逆运算,差分是前缀和的逆运算,差分是前缀和的逆运算

打了四遍(皮)

于是就有了前缀和维护差分和差分维护前缀和

我们先考虑一维差分

给你一个数列num,有n项,每次操作对一段区间加上一个数或减去一个数,最后询问数列中的各个元素是多少

要求做到$\Theta (操作数+数组大小)$

我们发现只有一次询问

所以可以差分

维护一个数组a[i],a[i]意义为num[i]比num[i+1]大多少

易得区间加操作只会改变 区间左端点-1 和 区间右端点 的a值

最后只需要求a[i]的前缀和(上面说过差分是前缀和的逆运算)就好了

于是这道题就被切了

 

下面我们把数列扩展到二维

先考虑二位前缀和

 在这张图中,黑点的意义为下图黑色区域的值的和

 

也就是左上区域

考虑怎么求出这个值

显然可以由上面的格子的前缀和与左面的格子的前缀和加和得到

但是这样的话,下图中的黑色区域会被计算两次

 

 明显算多了

那么就减去它,即:

　　a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]

那么考虑差分

始终记住一句话:差分是前缀和的逆运算

我们考虑对于一个点,那些点的差分值对它有贡献

对于下图中的黑点

 

 

 下图中的黑色部分都可以对它产生贡献

 

那么假如我们希望让下图的黑色区域的值都加一

 

 

 

我们可以让下图的黑色点的差分值加一

 

 

 

 

这样

黑色部分就全都加了1

但是我们明显加多了

黑色部分都被多加了1

那就减掉!

于是我们又把这两个黑点的差分值-1

好像OK了?

然而

细心的你应该会发现

我们把下图中的点多减了1

那么我们再

 

把这个黑点的差分值加1

这样就对了吧

ok,让我们捋一捋

我们先简单粗暴地把左上角的差分值加1

但发现加多了

于是有把加多的部分减掉了

又发现减多了

于是又把减多的加上了

加---减---加

这就是二维差分的方法

 明白了?现在进入hard模式

考虑在二维情况下的三角差分

对,我们要把形如下图的部分加1

 思考一下*1

 思考一下*2

思考一下*3

思考一下*4

思考一下*5

思考一下*6

思考一下*7

思考一下*8

思考一下*9

思考一下*10

思考时间到了!!!

接下来公布思路:

我们仍然需要四边形的差分,但要再引入一个三角形的差分

在这个新的差分中

下图黑点的作用范围将是下下张图

变成三角了有目有

考虑如何加1

我们可以先在黑点处加一

 

 

 那我们就会将下图的黑色区域加一

 

 

于是我们加多了对吧

参照刚刚的总结

接下来我们该减了

但我们加多的区域是一个梯形

 

显然不是只用三角形可以维护的

但是这是个直角梯形

还能被拆成一个四边形+一个三角形

于是我们可以将蓝色点的四边形的差分-1,绿色点的三角形差分-1(终于不是黑白双色的图了)

 

于是我们这次减多了

黑色部分被多减了1(又变成黑白双色的图了)

那就加1

于是,完结!!!

转载于:https://www.cnblogs.com/ooovooo/p/11603429.html

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

9.28 的相关文章

  • authorization权限控制_shiro入门学习--授权（Authorization）|筑基初期

    写在前面 经过前面的学习 xff0c 我们了解了shiro中的认证流程 xff0c 并且学会了如何通过自定义Realm实现应用程序的用户认证 在这篇文章当中 xff0c 我们将学习shiro中的授权流程 授权概述 这里的授权指的是授予某一系

  • Spring Boot+Spring Security+JWT 实现 RESTful Api 认证（二）

    摘要 上一篇Spring Boot 43 Spring Security 43 JWT 实现 RESTful Api 认证 xff08 一 xff09 我们已经sql教程 实现了基本的登录和token认证接口 xff0c 但是这里有个问题

  • vmware vsphere各版本差别，及各套件差别

    最近要开始全面支持虚拟化了 xff0c 客户私有云环境用的多的为vmware vsphere xff0c 特地恶补下vmware vsphere的各个差别 首先是vSphere xff0c ESXi和vCenter 的区别 ESXi vSp

  • 第五周课程总结&试验报告（三）

    第五周课程总结 xff1a 一 xff1a String类 1 xff1a 实例化String对象 xff0c String可以采取直接赋值的方式进行操作 xff1b 2 xff1a 61 61 可以用来进行内容的比较 xff0c 但是单纯

  • CSS3 选择器

    CSS3 选择器 在 CSS 中 xff0c 选择器是一种模式 xff0c 用于选择需要添加样式的元素 34 CSS 34 列指示该属性是在哪个 CSS 版本中定义的 xff08 CSS1 CSS2 还是 CSS3 xff09 选择器例子例

  • JavaScript中使用typeof运算符需要注意的几个坑

    typeof是一个运算符 xff0c 它对操作数返回的结果是一个字符串 xff0c 有6种 只针对ES xff0c 不包含HOST环境对象 1 39 undefined 39 2 39 boolean 39 3 39 string 39 4

  • unity视频教程

    英雄联盟教程 http pan baidu com s 1i3rkMS9 密码 bv6r https pan baidu com share link shareid 61 2589856556 amp uk 61 371904234 li

  • 相册列表 鼠标悬停显示照片介绍

    lt DOCTYPE HTML PUBLIC 34 W3C DTD HTML 4 01 Transitional EN 34 34 http www w3 org TR html4 loose dtd 34 gt lt html gt lt

  • 图书管理系统（毕业论文）

    毕 业 设 计 论 文 题 目 xff1a 图书管理系统 院 系 xff1a 计算机学院 专 业 xff1a 软件技术 姓 名 xff1a XXX 指导教师 xff1a XX 2017年 10 月 23 日 1 引言 5 2 相关技术突破

  • C#中定义数组--字符串及数组操作

    一 一维 xff1a int numbers 61 new int 1 2 3 4 5 6 不定长 int numbers 61 new int 3 1 2 3 定长 二 多维 int numbers 61 new int 1 2 3 1

  • 迭代器分类

    输入迭代器 读 xff0c 不能写 xff1b 只支持自增运算 istream iterator 61 61 61 43 43 gt 输出迭代器 写 xff0c 不能读 xff1b 只支持自增运算 ostream iterator 43 4

  • VC++中隐藏代码

    1 引言 在VS编辑器中可以对类中的方法 注释等内容进行隐藏 xff0c 单击左侧的 号即可完成隐藏 xff0c 隐藏后变为 43 xff0c 单击 43 号可以将隐藏的代码展开 2 隐藏任意代码 如果想在编辑器中隐藏任意代码段 xff0c

  • 常见签名算法之SHA256withRSA

    概述 在https blog csdn net chinoukin article details 100934995章节中 xff0c 我介绍了用Hmac算法用于签名算法中的方法 xff0c 本章节中将对常见的签名算法 SHA256wit

  • httpclient4封装类与HttpParser封装类

    httpclient4封装类与HttpParser封装类 最近工作中需要做一个爬虫去抓取指定页面的一些内容 xff0c 准备使用HttpParser来解析页面结构 xff0c 顺便看了一下httpclient4 xff0c 可以将它们配合使

  • 【Linux操作系统分析】进程——进程切换，进程的创建和撤销

    1 进程 进程是程序执行时的一个实例 xff0c 可以把它看作充分描述程序已经执行到何种程度的数据结构的汇集 从内核的观点看 xff0c 进程的目的是担当分配系统资源 xff08 CPU时间 xff0c 内存等 xff09 的实体 xff0

  • C++中的.和::和：和->的区别

    在学习C 43 43 的过程中我们经常会用到 和 和 xff1a 和 gt xff0c 在此整理一下这些常用符号的区别 1 A B则A为对象或者结构体 xff1b 2 A gt B则A为指针 xff0c gt 是成员提取 xff0c A g

  • 通过Curl 对url进行encode操作

    最近做项目的时候 xff0c 通过 Gflags Reload 时候 发现对于某些value中包含 61 中文等字符的支持不够好 xff0c value被截断了 经过分析后 xff0c 发现程序对url切分是用 61 amp 为标准的 xf

  • STM32进阶之串口环形缓冲区实现（转载）

    转载自微信公众号 玩转单片机 xff0c 感谢原作者 杰杰 队列的概念 在此之前 xff0c 我们来回顾一下队列的基本概念 xff1a 队列 Queue xff1a 是一种先进先出 First In First Out 简称 FIFO 的线

  • 位和结构体寄存器访问方法（转）

    1 2 1 传统 define 方法 1 2 外设位域结构体方法综述 DSP281x 头文件和外设示例使用位域结构体方法 xff0c 映射和访问基于F28x 外设寄存器 本节将介绍这种方法 xff0c 并把它和传统的 define 方法加以

  • 关于将函数写入头文件问题(分离式编译)

    如果某些函数在其他很多 cpp 文件中被调用 xff0c 那么为了避免写大量重复的代码以及让代码量更小一些 xff0c 我们可以将这些函数写头文件中 xff0c 然后其他 cpp 文件只需要引用该头文件然后就可以使用包含在头文件中的函数了

随机推荐

  • SpringSecurity配置跨域访问

    说明 java后端web服务有很多种方法可以实现跨域访问 xff0c 配置很简单 xff0c 今天这里我们用SpringSecurity的方式配置跨域访问 xff0c 配置方法如下 xff1a span class token keywor

  • 嵌入式C语言开发---存储器与寄存器

    概述 xff1a 讲述如何使用C语言来对底层寄存器进行封装 内容 xff1a 存储器映射寄存器与寄存器映射C语言访问寄存器 存储器映射 程序存储器 数据存储器 寄存器和I O 端口排列在同一个顺序的4 GB 地 址空间内 存储器映射 xff

  • httplib用法

    httplib的内容上是很多 xff0c 也比较简单 以下是一个非常简单的例子 xff0c 使用httplib获取google首页的html xff1a import httplib conn 61 httplib HTTPConnecti

  • HTTP认证之摘要认证——Digest（一）

    导航 HTTP认证之基本认证 Basic xff08 一 xff09 HTTP认证之基本认证 Basic xff08 二 xff09 HTTP认证之摘要认证 Digest xff08 一 xff09 HTTP认证之摘要认证 Digest x

  • Linux 文件名和路径的最大长度

    在x86 64 Linux下 xff0c 文件名的最大长度是255个字符 characters xff0c 文件路径的最大长度是4096字符 characters xff0c 即可以包含16级的最大文件长度的路径 在 lt limits h

  • Django之auth

    一 xff1a auth基础 xff08 1 xff09 作用 xff1a django提供给开发人员 对用户进行操作的模块的 例如 xff1a 登录 注册 认证 注销等等 xff08 2 xff09 使用方式 from django co

  • [JavaSE 源码分析] 关于HashMap的个人理解

    目录 HashMap是什么 HashMap的底层数据结构是什么 table容量为什么必须是二的倍数 table容量怎么做到二的倍数 Entry是怎样的结构 Node Entry在HashMap中的具体实现处理hash冲突的方法HashMap

  • HIS（LIS、PACS、RIS、EMR）系统简介

    HIS xff08 LIS PACS RIS EMR xff09 系统简介 HIS xff1a 医院信息系统 Hospital Information System HIS xff0c 利用电子计算机和通讯设备 xff0c 为医院所属各部

  • jackson使用问题:mapper.readValue()将JSON字符串转反序列化为对象失败或异常

    问题根源 xff1a 转化目标实体类的属性要与被转JSON字符串总的字段 一 一对应 xff01 字符串里可以少字段 xff0c 但绝对不能多字段 先附上我这段出现了问题的源码 xff1a 1 接收并转化相应的参数 需要在pom xml中引

  • SpringSecurity集成oauth2(jwt)

    版本 springboot版本 xff1a 2 2 7 RELEASE spring security oauth2版本 xff1a 2 3 6 RELEASE 主要依赖 span class token tag span class to

  • 微信小程序开发——点击按钮获取用户授权没反应或反应很慢的解决方法

    异常描述 xff1a 点击按钮获取用户手机号码 xff0c 有的时候会出现点击无反应 或很久之后才弹出用户授权获取手机号码的弹窗 xff0c 这种情况下 xff0c 也会出现点击穿透的问题 xff08 详见 xff1a 微信小程序开发 连续

  • 09-cmake语法-add_dependencies()

    在编译器的命令行上 xff0c 为当前路径以及下层路径的源文件加入一些define flag 这个命令可以用来引入任何flag xff0c 但是它的原意是用来引入预处理器的定义 那些以 D或 D开头的 看起来像预处理器定义的flag xff

  • WordPress教程之判断文章所属分类函数in_category、is_category

    最近自己在修改一个采用Wordpress程序的博客的时候需要用到一个特殊的功能 xff1a 我需要判断这篇文章是属于哪些分类 xff0c 如果属于我设定的分类下的文章 xff0c 则输出一个DIV内容 按道理说实现这个功能应该不算太难 xf

  • 对SIP摘要认证方案的理解

    一 口令认证常见机制 基于口令认证的系统一般有以下几种口令验证方式 xff1a 1 客户端以明文形式将用户名密码通过网络发送到服务器 xff0c 服务器与已经保存在服务端的用户名密码进行比较 xff0c 一致则通过验证 xff1b HTTP

  • 第三方库引用：头文件和库文件

    附加库与头文件目录 xff1a 1 头文件 头文件引用时的查找路径 xff1a c c 43 43 gt general 将第三方库的头文件所在文件夹包含进去 影响到文件中 h头文件的引用路径的写法 源码 xff1a include a h

  • 深入理解Java虚拟机JVM

    JVM工作原理和特点主要是指操作系统装入JVM是通过jdk中Java exe来完成 通过下面4步来完成JVM环境 1 创建JVM装载环境和配置 2 装载JVM dll 3 初始化JVM dll并挂界到JNIENV JNI调用接口 实例 4

  • Kubernetes Pod的数据卷Volume

    概述 由于容器本身是非持久化的 xff0c 因此需要解决在容器中运行应用程序遇到的一些问题 首先 xff0c 当容器崩溃时 xff0c kubelet将重新启动容器 xff0c 但是写入容器的文件将会丢失 xff0c 容器将会以镜像的初始状

  • Nodejs模块依赖的几种方式

    a js function add x y return x 43 y function sub x y return x y let str 61 34 God like 34 const arr 61 1 2 3 4 exports a

  • 9.26

    以后可能会在每次考试后 当然极大概率咕咕咕 找一道题讲讲其实是三道题太多了 那么既然量减了 质量就会提上去了也不一定 一次可能会根据某一道题说些思路 反正也没人看 随便写一些留着自己用好了 于是本期节目为您带来 换根dp 这东西好像考了两三

  • 9.28

    昨天的大概就咕咕咕了 今天说差分 多图预警 于是 进入正题 今天的主题是差分 但我们或许也应该先说说前缀和 众所周知 差分是前缀和的逆运算 跟我一起念三遍 差分是前缀和的逆运算 差分是前缀和的逆运算 差分是前缀和的逆运算 差分是前缀和的逆运

热门标签