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

树状数组 3 ：区间修改，区间查询

news 来源：原创 2025/7/21 18:17:35

【题目描述】

这是一道模板题。

给定数列 a[1],a[2],…,a[n]，你需要依次进行q个操作，操作有两类：

1lrx：给定 l,r,x对于所有 i∈[l,r]，将a[i]加上x（换言之，将 a[l],a[l+1],…a[r] 分别加上 x）；

2lr：给定 l,r求 ∑ri=la[i]的值（换言之，求 a[l]+a[l+1]+⋯+a[r] 的值）。

【输入格式】

第一行包含 2 个正整数 n,q表示数列长度和询问个数。保证 1≤n,q≤1000000。

第二行 n 个整数 a[1],a[2],…a[n]，表示初始数列。保证 |a[i]|≤1000000。

接下来 q 行，每行一个操作，为以下两种之一：

1lrx：对于所有 i∈[l,r]将 a[i] 加上 x；

2lr：输出 ∑ri=la[i]的值。

保证 1≤l≤r≤n,|x|≤1000000。

【输出格式】

对于每个 2lr 操作，输出一行，每行有一个整数，表示所求的结果。

样例

【输入】

【输出】

数据范围与提示

对于所有数据，1≤n,q≤1000000,|a[i]|≤1000000,1≤l≤r≤n,|x|≤1000000。

#include<bits/stdc++.h>
using namespace std;const int maxn = 1e6 + 7;
long long n, q, a[maxn],  t[maxn], t1[maxn];long long lowbit(int x) {return x & (-x);
}void change(int x, long long y) {for (int i = x; i <= n; i += lowbit(i)) {t[i] += y;t1[i] += y * x;}
}long long ans(int x) {long long ans = 0;for (int i = x; i; i -= lowbit(i)) {ans += (x + 1) * t[i] - t1[i];}return ans;
}int main() {scanf("%lld%lld", &n, &q);for (int i = 1; i <= n; i++) {scanf("%lld", &a[i]);change(i, a[i] - a[i - 1]);}for (int i = 1; i <= q; i++) {long long k, l, r, x;scanf("%lld%lld%lld", &k, &l, &r);if (k == 1) {scanf("%lld", &x);change(l, x);change(r + 1, -x);} else {printf("%lld\n", ans(r) - ans(l - 1));}}return 0;
}

树状数组 3 ：区间修改，区间查询

【题目描述】这是一道模板题。给定数列 a[1],a[2],…,a[n]，你需要依次进行q个操作，操作有两类： 1lrx：给定 l,r,x对于所有 i∈[l,r]，将a[i]加上x（换言之，将 a[l],a[l1],…a[r] 分别加上 x&a…...

编程日记 2025/7/21 18:17:35

C++的IO流

1. C语言的输入与输出 C语言中我们用到的最频繁的输入输出方式就是scanf ()与printf()。 scanf(): 从标准输入设备(键盘)读取数据，并将值存放在变量中。printf(): 将指定的文字/字符串输出到标准输出设备(屏幕)。注意宽度输出和精度输出控制。C语言借助了相应的缓…...

编程日记 2025/7/21 18:11:32

QLoRA和LoRA 微调

QLoRA 其实是一种结合了量化和 LoRA 微调技术的统一方法，而不是同时使用两种不同的微调方式。换句话说，QLoRA 的意思就是：先把大模型的主权重用低精度（例如 4-bit）量化，从而大幅减少存储需求；然…...

编程日记 2025/7/21 18:10:37

Android电话监听器的设计与实现：深入解析Service与TelephonyManager

目录一、引言二、Service核心机制解析 1. Service的本质特性 2. 生命周期管理 3. 服务类型全景三、Service实战开发 1. 启动式Service开发（lesson1） 2. 绑定式Service开发四、电话监听器完整实现（lesson3） 1. 系统架…...

编程日记 2025/7/19 14:01:49

java学习笔记7——面向对象

关键字：static 类变量静态变量的内存解析： 相关代码： public class ChineseTest {public static void main(String[] args) {System.out.println(Chinese.nation); //null 没赋值前System.out.println(Chinese.nation); //中国静态变量赋值…...

编程日记 2025/7/18 1:10:39

java学习——函数式编程（1）

函数式编程 Java 的函数式编程是一种以函数为核心构建逻辑的编程范式，强调不可变性、声明式代码和无副作用的操作。它通过Lambda表达式、函数式接口（如Function、Predicate、Consumer等）和Stream API等特性实现，将计算过程抽象为函数的组合与转换，而非传统的命令式步骤。…...

编程日记 2025/7/21 18:02:58

指定图片集合下载到指定文件夹 import java.io.*; import java.net.HttpURLConnection; import java.net.URL; import java.util.Arrays; import java.util.List;public class OfficeFileDownloader {/*** 需要下载的Office文档URL列表*/private static final List<Strin…...

编程日记 2025/7/17 7:43:46

Python爬虫：Feapder 的详细使用和案例

更多内容请见：爬虫和逆向教程-专栏介绍和目录文章目录 1. Feapder 概述1.1 Feapder介绍1.2 Feapder 核心特点1.3 Feapder 主要组件1.4 Feapder的安装2. 基础爬虫编写2.1 创建爬虫2.2 运行爬虫3. 数据采集案例3.1 新闻网站采集3.2 电商商品采集3.3 使用 Spider 类创建更强大爬…...

编程日记 2025/7/16 17:29:16

【江协科技STM32】读写备份寄存器RTC实时时钟（学习笔记）

参考相关文章理解： 【江协科技STM32】Unix时间戳（学习笔记）-CSDN博客【江协科技STM32】BKP备寄存器&RTC实时时钟（学习笔记）_stm32断电保存时钟-CSDN博客读写备份寄存器接线图：VBAT是从STLINK的…...

编程日记 2025/7/21 17:34:13

Linux touch命令

参考资料 Linux 常用命令 - touch 【创建空文件与修改时间戳】目录一. 用法简介二. 配合扩展字符，批量创建文件三. 修改文件的时间戳3.1 -t 配置项3.2 -d 配置项3.3 配合find命令实现批量时间戳修改四. 结合 find 批量创建相同时间的新文件一. 用法简介 ⏹当指…...

编程日记 2025/7/20 20:46:11

PyTorch图像预处理--Compose

torchvision.transforms.Compose 是 PyTorch 中用于图像预处理的核心工具，可将多个图像变换操作组合成一个顺序执行的流水线。 ‌1. 定义与作用‌ ‌功能‌：将多个图像处理步骤（如缩放、裁剪、归一化等）串联为一个整体&#xff…...

编程日记 2025/7/18 15:46:31

CSP历年题解

CSP历年题解 csp历年题解，csp.cpp内容涵盖从2023年12月开始一直持续到第一次认证的所有前4题。所有的题解均为满分，在其中，有四道题非本人编写，而从网上搜集优质解答，并且已在文中附上了来源链接。其余则为自己编写&a…...

编程日记 2025/7/21 6:35:23

《索引江湖：B树索引与哈希索引的风云对决》

在数据库的神秘世界里，索引宛如一把把神奇的钥匙，帮助我们在海量数据中快速找到所需信息。而B树索引与哈希索引，则是其中两把最为耀眼的利刃，各自凭借独特的“武功秘籍”，在不同的应用场景中大放异彩。今天&#xff0c…...

编程日记 2025/7/18 17:11:28

java八股文之JVM

1.什么是程序计数器程序计数器是 JVM 管理线程执行的“定位器”，记录每个线程当前执行的指令位置，确保程序流程的连续性和线程切换的准确性。线程私有的，每个线程一份，内部保存的字节码的行号。用于记录正在执行的字节码指令的地…...

编程日记 2025/7/16 17:06:43

学习爬虫的第二天——分页爬取并存入表中

阅读提示：我现在还在尝试爬静态页面一、分页爬取模式以豆瓣Top250为例： 基础url:豆瓣电影 Top 250https://movie.douban.com/top250 分页参数:?start0（第一页）、?start25（第二页）等每页显示25条数…...

编程日记 2025/7/17 12:18:36

Ubuntu与Windows之间相互复制粘贴的方法

一、打开Ubuntu终端二、卸载已有的工具 sudo apt-get autoremove open-vm-tools 三、安装工具 sudo apt-get install open-vm-tools-desktop 四、重启直接输入reboot 注：有任何问题欢迎评论区交流讨论或者私信！...

编程日记 2025/6/28 4:54:27

docker安装hyperf环境，连接本机redis问题处理

错误信息显示“Connection refused”，这通常说明 Docker 容器内的 Hyperf 项目无法连接到你本机的 Redis 服务。 1. 容器内的 127.0.0.1 指向问题在 Docker 容器中，127.0.0.1 指的是容器本身，而不是宿主机（你的 Mac）…...

编程日记 2025/7/15 21:13:28

第12章:优化并发_《C++性能优化指南》notes

优化并发一、并发基础与优化核心知识点二、关键代码示例与测试三、关键优化策略总结四、性能测试方法论多选题设计题答案与详解多选题答案： 设计题答案示例一、并发基础与优化核心知识点线程 vs 异步任务核心区别：std::thread直接管理线程&#xf…...

编程日记 2025/7/10 16:18:29

Linux操作系统7- 线程同步与互斥7（RingQueue环形队列生产者消费者模型改进）

上篇文章：Linux操作系统7- 线程同步与互斥6（POSIX信号量与环形队列生产者消费者模型）-CSDN博客本篇代码仓库：myLerningCode/l36 橘子真甜/Linux操作系统与网络编程学习 - 码云 - 开源中国 (gitee.com) 目录一. 单生产单消费单保…...

编程日记 2025/7/17 19:31:41

学有所记——初探向量数据库Weaviate

目标： 了解向量数据库的连接、建库、插入数据、查询数据等基本用法以及关于语义相似度的一些基本概念。背景： 前段时间尝试在自己的电脑上搭建OllamaDify平台，体验并探索大模型的强大功能。在使用过程中，尤其是在搭建RAG知识库…...

编程日记 2025/7/20 21:45:19

Ardupilot开源无人机之Geek SDK进展2025Q2

Ardupilot开源无人机之Geek SDK进展2025Q2 1. 源由2. 内容汇总2.1 【jetson-fpv】“Caution - Hot surface. Dont touch.”2.2 【jetson-fpv】1080P/720P显示设备配置 3. 遗留问题3.1 高优先级3.1.1 【jetson-fpv】1080P60FPS AI分析视频卡顿，丢包3.1.2 【jetson-fp…...

编程日记 2025/7/16 1:48:59

深入理解K8s与Docker的关系：容器化技术的双雄

友情提示：本文内容由银河易创（https://ai.eaigx.com）AI创作平台gpt-4-turbo模型生成，仅供参考。在现代云计算及微服务架构的发展中，Docker与Kubernetes（K8s）作为两大核心技术，被广泛…...

编程日记 2025/7/18 10:49:15

QT高效文件I/O编程--实用指南与最佳实践

概述在软件开发过程中，文件输入输出（I/O）操作是数据持久化和交换的核心部分。无论是简单的日志记录还是复杂的数据集处理，高效的文件I/O操作对于应用的整体性能至关重要最佳实践一、选择合适的文件模式正确选择文件打开模式是确保操作意图明确且安全的第一步。不同…...

编程日记 2025/7/16 22:22:22

QT记事本

记事本应用程序提供了基本的文本编辑功能，支持文件的新建、打开、保存和另存为操作，同时具备修改提示和关闭窗口时的保存确认功能。使用 UTF - 8 编码确保了对多语言文本的支持。 1. 项目整体结构 main.cpp：程序的入口点，负责初…...

编程日记 2025/7/21 4:30:48

【leetcode hot 100 84】柱状图中最大的矩形

解法一：单调栈 class Solution {public int largestRectangleArea(int[] heights) {int len heights.length;int area 0;// 先做一些特殊判断if(len0){return 0;}if(len1){return heights[0];}// 进入栈后发现后面更短，可以得到当前这个能勾勒的面积 …...

编程日记 2025/7/17 20:44:46

Spring----ioc

1.Spring 是什么？ 通过前⾯的学习, 我们知道了Spring是⼀个开源框架, 他让我们的开发更加简单. 他⽀持⼴泛的应⽤场景, 有着活跃⽽庞⼤的社区, 这也是Spring能够⻓久不衰的原因. 但是这个概念相对来说, 还是⽐较抽象. 我们⽤⼀句更具体的话来概括Spring, 那就…...

编程日记 2025/7/21 17:35:10

C++——重载

目录一、函数重载基本概念函数重载的条件编程示例代码讲解函数重载的注意事项二、运算符重载什么是运算符重载？ 运算符重载的实质是什么？ 运算符重载函数的写法运算符重载的基本语法可重载的运算符列表基本原则编程示例代码解…...

编程日记 2025/7/16 16:53:21

答疑解惑：EMC VMAX3 MMCS控制台不定期重启原因分析

今天有个朋友咨询他们有一台EMC的VMAX100k设备，其中MMCS2的管理控制台定期重启，但始终无法找到重启原因，稍微花了点时间，帮客户看了下。先说结论，MMCS2确实不定期发生重启，每次reboot都是一样的message信息…...

编程日记 2025/7/11 5:23:10

单例模式（Singleton Pattern）

单例模式（Singleton Pattern） 任务管理器可以作为一个全局的任务配置管理类，使用单例模式保证全局只有一个实例。这样你可以避免在应用程序中创建多个任务管理对象，保持配置参数的统一。示例： class TaskManager { …...

编程日记 2025/7/17 1:10:26

树莓派超全系列文档--(8)RaspberryOS实用程序

RaspberryOS实用程序实用程序kmsprintvclogvcgencmdvcosversionget_throttledmeasure_tempmeasure_clock [clock]measure_volts [block]otp_dumpget_config [configuration item|int|str]get_mem typecodec_enabled [type]mem_oommem_reloc_statsread_ring_osc 文章来源&#…...

编程日记 2025/7/17 9:15:52

Rust 与 FFmpeg 实现视频水印添加：技术解析与应用实践

引言在短视频、直播、影视制作等领域，视频水印是一种常见的工具，用于保护版权、提升品牌辨识度或满足合规性要求。然而，开发者在实现水印添加时往往面临以下挑战： 手动处理效率低：使用图像编辑软件（如 P…...

编程日记 2025/7/16 11:39:04

绿联NAS安装内网穿透实现无公网IP也能用手机平板远程访问经验分享

文章目录前言1. 开启ssh服务2. ssh连接3. 安装cpolar内网穿透4. 配置绿联NAS公网地址前言大家好，今天给大家带来一个超级炫酷的技能——如何在绿联NAS上快速安装cpolar内网穿透工具。想象一下，即使没有公网IP，你也能随时随地远程访问自己…...

编程日记 2025/7/15 1:15:29

如何在 React 项目中使用React.lazy和Suspense实现组件的懒加载？

大白话如何在 React 项目中使用React.lazy和Suspense实现组件的懒加载？ 在 React 项目里，有时候组件功能多、体积大，要是一次性把所有组件都加载进来，网页加载速度就会变慢。而 React 提供了 React.lazy 和 Suspense 这两个好东西…...

编程日记 2025/7/18 5:16:11

虫洞数观系列一 | 豆瓣电影TOP250数据采集与MySQL存储实战

目录系列文章 1. 引言 2 技术栈Request 2.1请求头headers 2.2查找定位信息 2.3处理网页html结构化数据 2.4每页url规律 2.5逐条查找所需信息 2.6完整代码 3 数据存储至mysql 3.1新建数据库 3.2编写数据库写入py文件 3.2.1构建1个执行sql语句的函数 3.2.2构造一个…...

编程日记 2025/7/17 11:42:12

模型阿米巴模式

系列文章分享模型，了解更多👉 模型_思维模型目录。小团队独立经营，企业活力无限。 1 阿米巴模式的应用 1.1 日航重生（航空业成功案例） 应用领域航空运输业破产重组与组织激活案例名称日本航空（JAL&…...

编程日记 2025/7/18 5:01:30

针对stm32F103C8t6芯片调节USB串口的经验

1、首先这是自己手搓的板子，对于之前一直没有了解过USB这方面，则这个针对USB部分没有设计上拉电阻，造成不管怎么调节PC端都没有反应。图一这个没有添加1.5K电阻这个D+位置应该再接一个1.5KR的电阻如图2所示图2 这样调节的话PC端就可以识别到USB串口，但是这是串口还是会…...

编程日记 2025/7/12 1:42:35

JVM详解(包括JVM内存模型与GC垃圾回收)

📖前言： 学会使用Java对于一个程序员是远远不够的。Java语法的掌握只是一部分，另一部分就是需要掌握Java内部的工作原理，从编译到运行，到底是谁在帮我们完成工作的？ 接下来着重对Java虚拟机，也就…...

编程日记 2025/7/18 13:56:53

解锁DeepSeek潜能：Docker+Ollama打造本地大模型部署新范式

🐇明明跟你说过：个人主页 🏅个人专栏：《深度探秘：AI界的007》 🏅 🔖行路有良友，便是天堂🔖 目录一、引言 1、什么是Docker 2、什么是Ollama 二、准备工作 1、操…...

编程日记 2025/7/16 1:37:51

【Linux网络】——Socket网络编程

前言在当今数字化的时代，网络通信已经成为计算机领域不可或缺的一部分。无论是日常的网页浏览、社交媒体交互，还是大规模的企业级数据传输，都离不开高效可靠的网络通信。而在Linux操作系统中，Socket网络编程是实现各种网络应用的…...

编程日记 2025/7/17 8:45:20

基于javaweb的SpringBoot雪具商城系统设计与实现(源码+文档+部署讲解）

技术范围：SpringBoot、Vue、SSM、HLMT、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、小程序、安卓app、大数据、物联网、机器学习等设计与开发。主要内容：免费功能设计、开题报告、任务书、中期检查PPT、系统功能实现、代码编写、论文编写和辅导、论…...

编程日记 2025/7/11 15:03:01

Android 简化图片加载与显示——使用Coil和Kotlin封装高效工具类

为了简化使用Coil加载网络图片和GIF的过程，我们可以封装一个工具类。这个工具类将包括初始化ImageLoader的方法、加载图片到ImageView的方法，以及可能的其他便捷方法，如加载圆形图片、设置占位图等。下面是一个示例： 首先&#x…...

编程日记 2025/7/18 18:33:31

Flink watermark的时间字段有空值，建表的时候，如何处理

在 Flink 中处理时间字段存在空值时，需通过表定义阶段的特殊处理和 Watermark 生成策略调整来避免因空值导致的窗口计算异常或任务失败。以下是具体解决方案及实现方法： 1. 空值处理核心策略 1.1 查询时，过滤空值数据（推荐&am…...

编程日记 2025/7/10 5:20:08

关于matlab和python谁快的问题

关于matlab和python谁快的问题，python比matlab在乘法上快10倍，指数计算快4倍，加减运算持平，略慢于matlab。或许matlab只适合求解特征值。 import torch import timen 50000 # 矩阵规模 M torch.rand(n, 31)start_time time.t…...

编程日记 2025/7/16 20:17:38

【DevOps】DevOps and CI/CD Pipelines

DevOps 是一种将开发与运维实践相结合的模式，旨在缩短软件开发周期并交付高质量软件。 DevOps 是什么？ 开发团队与运维团队之间的协作 • 持续集成与持续交付（CI/CD） • 流程自动化 • 基础设施即代码（IaC）…...

编程日记 2025/7/17 14:14:40

ROS--IMU数据包

IMU惯性测量单元一：IMU二：ROS中三：IMU数据包三：总结提示：以下是本篇文章正文内容，下面案例可供参考一：IMU IMU（Inertial Measurement Unit，惯性测量单元&#xff09…...

编程日记 2025/7/16 16:01:57

【机器学习】手撕封装PCA——将高维数据映射到低维数据的过程

PCA将高维数据映射到低维数据的过程一、摘要二、PCA的降维思路三、PCA代码实现降维过程3.1 PCA类的实现与封装3.2 PCA类的使用示例四、PCA的恢复过程一、摘要本文详细介绍了主成分分析法（PCA）在高维数据降维中的应用。首先，阐述了PCA的基…...

编程日记 2025/7/14 18:49:04

LangChain开发（七）自定义输出格式（JSON/XML/YAML）

文章目录 JSON结构输出未使用PydanticPydantic流式处理 XML结构输出xml输出指定字段 YAML输出源码地址参考资料 JSON结构输出虽然一些模型提供商支持内置的方法返回结构化输出，但并非所有都支持。我们可以使用输出解析器来帮助用户通过指示指定任意的JSON模型&…...

编程日记 2025/7/19 23:25:40

RustDesk部署到linux(自建服务器)

简介 ‌RustDesk‌是一款开源的远程桌面软件，由中国开发者开发，使用Rust编程语言构建。它支持跨平台运行，可以在Windows、macOS、Linux、iOS、Android和Web等多个平台上使用。RustDesk的主要功能包括远程桌面访问、文件传输、文本聊天等&…...

编程日记 2025/7/21 9:35:53

分布式锁，redisson，redis

目录什么是分布式锁分布式锁解决什么问题分布式锁的特点使用分布式锁的场景怎么使用分布式锁1. 添加依赖2. 配置 Redisson 客户端3. 使用 Redisson 实现分布式锁什么是分布式锁分布式锁是一种锁机制，用于在分布式环境下，解决多个线程并发访问同一共享…...

编程日记 2025/7/13 21:19:32

linux常用指令（9）

加油同志们,我们离胜利不远了,再有两天我们就可以了解完linux的一些基本常用指令了,到时我们便可以进入一些shell脚本语法了,那么话不多说,来看. 1.more指令功能描述：more指令是一个基于vi编辑器的文本过滤器,它以全屏幕的方式按页显示文本文件的内容. 基本语法…...

编程日记 2025/7/19 4:51:38