第五十七章 树状数组(二)
第五十七章 树状数组(二)
- 一、差分的缺陷
- 二、树状数组与差分
- 三、例题
- 题目描述
- 输入格式
- 输出格式
- 样例 #1
- 样例输入 #1
- 样例输出 #1
- 提示
- 样例 1 解释:
- 数据规模与约定
- 代码
一、差分的缺陷
差分的作用是能够在O(1)的时间内给一段区间加上相同的数字,最终查询的时候, 只需要对差分数组求前缀和即可。
但是,如果我们修改一次就想查询一次某个点的值的话。就说明我们需要不断地去求前缀和,即我们每次查询的时间复杂度都是O(n)O(n)O(n)的。这个是非常低效的。
因此,我们就可以利用树状数组来进行优化求解。
二、树状数组与差分
作者在之前的文章中介绍过树状数组与前缀和的关系,没有看过的话,作者建议先去看之前的文章:第五十六章 树状数组(一)
在前缀和+树状数组的题目中,我们是将原数组包装成了树状数组。
而在差分+树状数组的题目中,我们需要将原数组的差分数组写作树状数组的形式。
这样的话,如果给原数组[l,r]内的元素加上一个x的话,我们只需要操作差分数组中的两个点即可。这就又转化为我们在之前的文章中介绍的树状数组的三个函数。
三、例题
洛谷:P3368 【模板】树状数组 2
题目描述
如题,已知一个数列,你需要进行下面两种操作:
-
将某区间每一个数加上 xxx;
-
求出某一个数的值。
输入格式
第一行包含两个整数 NNN、MMM,分别表示该数列数字的个数和操作的总个数。
第二行包含 NNN 个用空格分隔的整数,其中第 iii 个数字表示数列第 $i $ 项的初始值。
接下来 MMM 行每行包含 222 或 444个整数,表示一个操作,具体如下:
操作 111: 格式:1 x y k
含义:将区间 [x,y][x,y][x,y] 内每个数加上 kkk;
操作 222: 格式:2 x
含义:输出第 xxx 个数的值。
输出格式
输出包含若干行整数,即为所有操作 222 的结果。
样例 #1
样例输入 #1
5 5
1 5 4 2 3
1 2 4 2
2 3
1 1 5 -1
1 3 5 7
2 4
样例输出 #1
6
10
提示
样例 1 解释:
故输出结果为 6、10。
数据规模与约定
对于 30%30\%30% 的数据:N≤8N\le8N≤8,M≤10M\le10M≤10;
对于 70%70\%70% 的数据:N≤10000N\le 10000N≤10000,M≤10000M\le10000M≤10000;
对于 100%100\%100% 的数据:1≤N,M≤5000001 \leq N, M\le 5000001≤N,M≤500000,1≤x,y≤n1 \leq x, y \leq n1≤x,y≤n,保证任意时刻序列中任意元素的绝对值都不大于 2302^{30}230。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 10;
int a[N], b[N], tree[N];
int n, m;int lowbits(int x)
{return x & -x;
}void add(int pos, int x)
{for(int i = pos; i <= n; i += lowbits(i))tree[i] += x;
}int quary(int pos)
{int res = 0;for(int i = pos; i; i -= lowbits(i))res += tree[i];return res;
}void solve()
{cin >> n >> m;for(int i = 1; i <= n; i ++ )cin >> a[i];for(int i = 1; i <= n; i ++ ){b[i] = a[i] - a[i - 1];add(i, b[i]);}while(m -- ){int op;cin >> op;if(op == 1){int l, r, d;cin >> l >> r >> d;add(l, d);add(r + 1, -d);}else{int pos;cin >> pos;cout << quary(pos) << endl;}}}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);solve();
}
相关文章:

第五十七章 树状数组(二)
第五十七章 树状数组(二)一、差分的缺陷二、树状数组与差分三、例题题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1提示样例 1 解释:数据规模与约定代码一、差分的缺陷 差分的作用是能够在O(1)的时间内给一段区间加上相同的数字&am…...
比特币的网络
比特币的网络 1. DNS-seed 在比特币网络中,初始节点发现一共有两种方式。 第一种叫做 DNS-seed,又称 DNS 种子节点,DNS 就是中心化域名查询服务,比特币的 社区维护者会维护一些域名。 比如 seed.bitcoin.sipa.be 这个域名就是由比特币的核心开发者 Sipa 维护的,如果我…...
ChatGPT的模型介绍及GO语言实现API
ChatGPT除了大家熟悉的GPT3之外,还有其他辅助模型,比如处理代码的以及有害信息过滤的系统。总的来说是下面三个组成:GPT-3:一组能够理解和生成自然语言的模型CodexLimited beta:一组可以理解和生成代码的模型ÿ…...

Tile防丢器引入全新防盗模式,苹果Find My功能拓展到大众消费电子
Tile 宣布引入全新的防盗模式,Tile 配件启用之后,反跟踪扫描和安全功能就无法检测到该配件。Tile 为了遏制其物品追踪产品用于追踪某人,此前推出了 Scan and Secure 功能。iPhone 和安卓用户可以通过该功能扫描附近的 Tile 设备,以…...

物联网中RocketMQ的使用
物联网中RocketMQ的使用 1. 背景 随着物联网行业的发展、智能设备数量越来越多,很多常见的智能设备都进入了千家万户;随着设备数量的增加,也对后台系统的性能提出新的挑战。 在日常中,存在一些特定的场景,属于高并发请…...

用Three.js搭建的一个艺术场景
本文翻译自于Medium,原作者用 Three.js 创建了一个“Synthwave 场景”,效果还不错,在此加上自己的理解,记录一下。在线Demo. 地形构建 作者想要搭建一个中间平坦、两侧有凹凸山脉效果并且能够一直绵延不断的地形,接下…...

算法导论【字符串匹配】—朴素算法、Rabin-Karp、有限自动机、KMP
算法导论【字符串匹配】—朴素算法、Rabin Karp、有限自动机、KMP朴素字符串匹配算法Rabin-Karp算法有限自动机KMP算法朴素字符串匹配算法 预处理时间:0匹配时间:O((n-m1)m) Rabin-Karp算法 预处理时间:Θ(m),需要预先算出匹…...

如何在 Python 中验证用户输入
要验证用户输入: 使用 while 循环进行迭代,直到提供的输入值有效。检查输入值在每次迭代中是否有效。如果该值有效,则跳出 while 循环。 # ✅ 验证用户输入的是否是整数num 0while True:try:num int(input("Enter an integer 1-10: …...

JVM详解——类的加载
文章目录类的加载1、Java程序如何运行2、Java字节码文件3、类加载4、类加载的过程5、类加载器6、类的加载方式7、类的加载机制8、双亲委派机制9、破坏双亲委派机制类的加载 1、Java程序如何运行 首先通过Javac命令将.java文件编译生成.class字节码文件。 Javac是Java编译命令&a…...

Ubuntu最新版本(Ubuntu22.04LTS)安装nfs服务器及使用教程
目录 一、概述 二、在Ubuntu搭建nfs服务器 👉2.1 安装nfs服务器 👉2.2 创建nfs服务器共享目录 👉2.3 修改nfs服务器配置文件 👉2.4 重启nfs服务器 三、客户端访问nfs服务器共享目录 🎈3.1 在nfs客户端挂载服…...

Python-第九天 Python异常、模块与包
Python-第九天 Python异常、模块与包一、了解异常1. 什么是异常:2. bug是什么意思:二、异常的捕获方法1. 为什么要捕获异常?2. 捕获异常的语法3. 如何捕获所有异常?三、异常的传递性1.异常是具有传递性的四、Python模块1. 什么是模…...

博彩公司 BetMGM 发生数据泄露,“赌徒”面临网络风险
Bleeping Computer 网站披露,著名体育博彩公司 BetMGM 发生一起数据泄露事件,一名威胁攻击者成功窃取其大量用户个人信息。 据悉,BetMGM 数据泄漏事件中,攻击者盗取了包括用户姓名、联系信息(如邮政地址、电子邮件地址…...

初探Mysql反向读取文件
前言 Mysql反向读取文件感觉蛮有意思的,进行了解过后,简单总结如下,希望能对在学习Mysql反向读取文件的师傅有些许帮助。 前置知识 在Mysql中存在这样一条语句 LOAD DATA INFILE它的作用是读取某个文件中的内容并放置到要求的表中&#x…...
地图坐标系大全:常用地图坐标系详解与转换指南
介绍地图坐标系的基本概念和原理地图坐标系是用于描述地图上位置的数学模型。它可以用来表示地球表面上的任意一个点,使得这个点的位置可以在地图上精确定位。不同的地图坐标系采用不同的基准面和投影方式,因此会有不同的坐标系参数,不同的坐…...

使用 URLSearchParams 解析和管理URL query参数
介绍 首先 URLSearchParams是一个构造函数,会生成一个URLSearchParams对象,参数类型: 不传 | string | object | URLSearchParams, 并且遇到特殊字符它会自动帮我们encode 和 decode const ur…...

一台电脑安装26个操作系统(windows,macos,linux,chromeOS,Android,静待HarmonyOS)
首先看看安装了哪些操作系统1-4: windows系统 四个5.Ubuntu6.deepin7.UOS家庭版8.fydeOS9.macOS10.银河麒麟11.红旗OS12.openSUSE Leap13.openAnolis14.openEuler(未安装桌面UI)15.中标麒麟(NeoKylin)16.centos17.debian Edu18.fedora19.oraclelinux(特别…...
Python配置文件管理之ini和yaml文件读取
1. 引言 当我们设计软件时,我们通常会花费大量精力来编写高质量的代码。但这往往还不够,一个好的软件还应该考虑其整个系统,如测试、部署、网络等。其中最重要的一个方面是配置管理。 良好的配置管理应允许在任何环境中执行软件而不更改代码…...

实战一(下):如何利用基于充血模型的DDD开发一个虚拟钱包系统?
上一节课,我们做了一些理论知识的铺垫性讲解,讲到了两种开发模式,基于贫血模型的传统开发模式,以及基于充血模型的DDD开发模式。今天,我们正式进入实战环节,看如何分别用这两种开发模式,设计实现一个钱包系统。话不多说,让我们正式…...
webpack当中的代码分割详解
A.代码分割方法一:将原来的单入口文件改为多入口文件 将不同的文件例如js代码文件分为入口文件和测试文件,这个时候打包出来的代码就会根据不同的文件单独打包成属于他们自己的文件 例如以下为单入口文件: entry: ./src/js/index.js 多入口文件:(在输出…...

【SSM】Spring对IoC的实现方式DI详讲
控制反转的一种实现方式——依赖注入一、IoC 控制反转(Overview)依赖注入(DI)- Overview利用 IoC(控制反转)这种思想有什么好处呢?二、依赖注入的方式setter 方式(xml配置中的proper…...
React 第五十五节 Router 中 useAsyncError的使用详解
前言 useAsyncError 是 React Router v6.4 引入的一个钩子,用于处理异步操作(如数据加载)中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误:捕获在 loader 或 action 中发生的异步错误替…...

docker详细操作--未完待续
docker介绍 docker官网: Docker:加速容器应用程序开发 harbor官网:Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台,用于将应用程序及其依赖项(如库、运行时环…...

23-Oracle 23 ai 区块链表(Blockchain Table)
小伙伴有没有在金融强合规的领域中遇见,必须要保持数据不可变,管理员都无法修改和留痕的要求。比如医疗的电子病历中,影像检查检验结果不可篡改行的,药品追溯过程中数据只可插入无法删除的特性需求;登录日志、修改日志…...

深入理解JavaScript设计模式之单例模式
目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式(Singleton Pattern&#…...

【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力
引言: 在人工智能快速发展的浪潮中,快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型(LLM)。该模型代表着该领域的重大突破,通过独特方式融合思考与非思考…...

Psychopy音频的使用
Psychopy音频的使用 本文主要解决以下问题: 指定音频引擎与设备;播放音频文件 本文所使用的环境: Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...

12.找到字符串中所有字母异位词
🧠 题目解析 题目描述: 给定两个字符串 s 和 p,找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义: 若两个字符串包含的字符种类和出现次数完全相同,顺序无所谓,则互为…...

GC1808高性能24位立体声音频ADC芯片解析
1. 芯片概述 GC1808是一款24位立体声音频模数转换器(ADC),支持8kHz~96kHz采样率,集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器,适用于高保真音频采集场景。 2. 核心特性 高精度:24位分辨率,…...

RabbitMQ入门4.1.0版本(基于java、SpringBoot操作)
RabbitMQ 一、RabbitMQ概述 RabbitMQ RabbitMQ最初由LShift和CohesiveFT于2007年开发,后来由Pivotal Software Inc.(现为VMware子公司)接管。RabbitMQ 是一个开源的消息代理和队列服务器,用 Erlang 语言编写。广泛应用于各种分布…...
Caliper 负载(Workload)详细解析
Caliper 负载(Workload)详细解析 负载(Workload)是 Caliper 性能测试的核心部分,它定义了测试期间要执行的具体合约调用行为和交易模式。下面我将全面深入地讲解负载的各个方面。 一、负载模块基本结构 一个典型的负载模块(如 workload.js)包含以下基本结构: use strict;/…...