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

第五十七章 树状数组(二)

第五十七章 树状数组(二)

  • 一、差分的缺陷
  • 二、树状数组与差分
  • 三、例题
    • 题目描述
    • 输入格式
    • 输出格式
    • 样例 #1
      • 样例输入 #1
      • 样例输出 #1
    • 提示
        • 样例 1 解释:
        • 数据规模与约定
    • 代码

一、差分的缺陷

差分的作用是能够在O(1)的时间内给一段区间加上相同的数字,最终查询的时候, 只需要对差分数组求前缀和即可。
但是,如果我们修改一次就想查询一次某个点的值的话。就说明我们需要不断地去求前缀和,即我们每次查询的时间复杂度都是O(n)O(n)O(n)的。这个是非常低效的。

因此,我们就可以利用树状数组来进行优化求解。

二、树状数组与差分

作者在之前的文章中介绍过树状数组与前缀和的关系,没有看过的话,作者建议先去看之前的文章:第五十六章 树状数组(一)

在前缀和+树状数组的题目中,我们是将原数组包装成了树状数组。

而在差分+树状数组的题目中,我们需要将原数组的差分数组写作树状数组的形式。

这样的话,如果给原数组[l,r]内的元素加上一个x的话,我们只需要操作差分数组中的两个点即可。这就又转化为我们在之前的文章中介绍的树状数组的三个函数。

三、例题

洛谷:P3368 【模板】树状数组 2

题目描述

如题,已知一个数列,你需要进行下面两种操作:

  1. 将某区间每一个数加上 xxx

  2. 求出某一个数的值。

输入格式

第一行包含两个整数 NNNMMM,分别表示该数列数字的个数和操作的总个数。

第二行包含 NNN 个用空格分隔的整数,其中第 iii 个数字表示数列第 $i $ 项的初始值。

接下来 MMM 行每行包含 222444个整数,表示一个操作,具体如下:

操作 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\le8N8M≤10M\le10M10

对于 70%70\%70% 的数据:N≤10000N\le 10000N10000M≤10000M\le10000M10000

对于 100%100\%100% 的数据:1≤N,M≤5000001 \leq N, M\le 5000001N,M5000001≤x,y≤n1 \leq x, y \leq n1x,yn,保证任意时刻序列中任意元素的绝对值都不大于 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();
}

相关文章:

第五十七章 树状数组(二)

第五十七章 树状数组&#xff08;二&#xff09;一、差分的缺陷二、树状数组与差分三、例题题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1提示样例 1 解释&#xff1a;数据规模与约定代码一、差分的缺陷 差分的作用是能够在O(1)的时间内给一段区间加上相同的数字&am…...

比特币的网络

比特币的网络 1. DNS-seed 在比特币网络中,初始节点发现一共有两种方式。 第一种叫做 DNS-seed,又称 DNS 种子节点,DNS 就是中心化域名查询服务,比特币的 社区维护者会维护一些域名。 比如 seed.bitcoin.sipa.be 这个域名就是由比特币的核心开发者 Sipa 维护的,如果我…...

ChatGPT的模型介绍及GO语言实现API

ChatGPT除了大家熟悉的GPT3之外&#xff0c;还有其他辅助模型&#xff0c;比如处理代码的以及有害信息过滤的系统。总的来说是下面三个组成&#xff1a;GPT-3&#xff1a;一组能够理解和生成自然语言的模型CodexLimited beta&#xff1a;一组可以理解和生成代码的模型&#xff…...

Tile防丢器引入全新防盗模式,苹果Find My功能拓展到大众消费电子

Tile 宣布引入全新的防盗模式&#xff0c;Tile 配件启用之后&#xff0c;反跟踪扫描和安全功能就无法检测到该配件。Tile 为了遏制其物品追踪产品用于追踪某人&#xff0c;此前推出了 Scan and Secure 功能。iPhone 和安卓用户可以通过该功能扫描附近的 Tile 设备&#xff0c;以…...

物联网中RocketMQ的使用

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

用Three.js搭建的一个艺术场景

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

算法导论【字符串匹配】—朴素算法、Rabin-Karp、有限自动机、KMP

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

如何在 Python 中验证用户输入

要验证用户输入&#xff1a; 使用 while 循环进行迭代&#xff0c;直到提供的输入值有效。检查输入值在每次迭代中是否有效。如果该值有效&#xff0c;则跳出 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服务器  &#x1f449;2.1 安装nfs服务器  &#x1f449;2.2 创建nfs服务器共享目录  &#x1f449;2.3 修改nfs服务器配置文件  &#x1f449;2.4 重启nfs服务器 三、客户端访问nfs服务器共享目录  &#x1f388;3.1 在nfs客户端挂载服…...

Python-第九天 Python异常、模块与包

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

博彩公司 BetMGM 发生数据泄露,“赌徒”面临网络风险

Bleeping Computer 网站披露&#xff0c;著名体育博彩公司 BetMGM 发生一起数据泄露事件&#xff0c;一名威胁攻击者成功窃取其大量用户个人信息。 据悉&#xff0c;BetMGM 数据泄漏事件中&#xff0c;攻击者盗取了包括用户姓名、联系信息&#xff08;如邮政地址、电子邮件地址…...

初探Mysql反向读取文件

前言 Mysql反向读取文件感觉蛮有意思的&#xff0c;进行了解过后&#xff0c;简单总结如下&#xff0c;希望能对在学习Mysql反向读取文件的师傅有些许帮助。 前置知识 在Mysql中存在这样一条语句 LOAD DATA INFILE它的作用是读取某个文件中的内容并放置到要求的表中&#x…...

地图坐标系大全:常用地图坐标系详解与转换指南

介绍地图坐标系的基本概念和原理地图坐标系是用于描述地图上位置的数学模型。它可以用来表示地球表面上的任意一个点&#xff0c;使得这个点的位置可以在地图上精确定位。不同的地图坐标系采用不同的基准面和投影方式&#xff0c;因此会有不同的坐标系参数&#xff0c;不同的坐…...

使用 URLSearchParams 解析和管理URL query参数

介绍 首先 URLSearchParams是一个构造函数&#xff0c;会生成一个URLSearchParams对象&#xff0c;参数类型&#xff1a; 不传 &#xff5c; string &#xff5c; object &#xff5c; URLSearchParams&#xff0c; 并且遇到特殊字符它会自动帮我们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.中标麒麟&#xff08;NeoKylin&#xff09;16.centos17.debian Edu18.fedora19.oraclelinux(特别…...

Python配置文件管理之ini和yaml文件读取

1. 引言 当我们设计软件时&#xff0c;我们通常会花费大量精力来编写高质量的代码。但这往往还不够&#xff0c;一个好的软件还应该考虑其整个系统&#xff0c;如测试、部署、网络等。其中最重要的一个方面是配置管理。 良好的配置管理应允许在任何环境中执行软件而不更改代码…...

实战一(下):如何利用基于充血模型的DDD开发一个虚拟钱包系统?

上一节课,我们做了一些理论知识的铺垫性讲解,讲到了两种开发模式,基于贫血模型的传统开发模式,以及基于充血模型的DDD开发模式。今天&#xff0c;我们正式进入实战环节&#xff0c;看如何分别用这两种开发模式&#xff0c;设计实现一个钱包系统。话不多说&#xff0c;让我们正式…...

webpack当中的代码分割详解

A.代码分割方法一&#xff1a;将原来的单入口文件改为多入口文件 将不同的文件例如js代码文件分为入口文件和测试文件&#xff0c;这个时候打包出来的代码就会根据不同的文件单独打包成属于他们自己的文件 例如以下为单入口文件: entry: ./src/js/index.js 多入口文件:(在输出…...

【SSM】Spring对IoC的实现方式DI详讲

控制反转的一种实现方式——依赖注入一、IoC 控制反转&#xff08;Overview&#xff09;依赖注入&#xff08;DI&#xff09;- Overview利用 IoC&#xff08;控制反转&#xff09;这种思想有什么好处呢&#xff1f;二、依赖注入的方式setter 方式&#xff08;xml配置中的proper…...

IDEA运行Tomcat出现乱码问题解决汇总

最近正值期末周&#xff0c;有很多同学在写期末Java web作业时&#xff0c;运行tomcat出现乱码问题&#xff0c;经过多次解决与研究&#xff0c;我做了如下整理&#xff1a; 原因&#xff1a; IDEA本身编码与tomcat的编码与Windows编码不同导致&#xff0c;Windows 系统控制台…...

测试微信模版消息推送

进入“开发接口管理”--“公众平台测试账号”&#xff0c;无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息&#xff1a; 关注测试号&#xff1a;扫二维码关注测试号。 发送模版消息&#xff1a; import requests da…...

在软件开发中正确使用MySQL日期时间类型的深度解析

在日常软件开发场景中&#xff0c;时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志&#xff0c;到供应链系统的物流节点时间戳&#xff0c;时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库&#xff0c;其日期时间类型的…...

【kafka】Golang实现分布式Masscan任务调度系统

要求&#xff1a; 输出两个程序&#xff0c;一个命令行程序&#xff08;命令行参数用flag&#xff09;和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽&#xff0c;然后将消息推送到kafka里面。 服务端程序&#xff1a; 从kafka消费者接收…...

python打卡day49

知识点回顾&#xff1a; 通道注意力模块复习空间注意力模块CBAM的定义 作业&#xff1a;尝试对今天的模型检查参数数目&#xff0c;并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】

微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来&#xff0c;Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...

全志A40i android7.1 调试信息打印串口由uart0改为uart3

一&#xff0c;概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本&#xff1a;2014.07&#xff1b; Kernel版本&#xff1a;Linux-3.10&#xff1b; 二&#xff0c;Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01)&#xff0c;并让boo…...

【Oracle】分区表

个人主页&#xff1a;Guiat 归属专栏&#xff1a;Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...

Device Mapper 机制

Device Mapper 机制详解 Device Mapper&#xff08;简称 DM&#xff09;是 Linux 内核中的一套通用块设备映射框架&#xff0c;为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程&#xff0c;并配以详细的…...

力扣-35.搜索插入位置

题目描述 给定一个排序数组和一个目标值&#xff0c;在数组中找到目标值&#xff0c;并返回其索引。如果目标值不存在于数组中&#xff0c;返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...