243. 一个简单的整数问题2(树状数组)

输入样例:

10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4

输出样例:

4
55
9
15

 解析:

        一般树状数组都是单点修改、区间查询或者单点查询、区间修改。这道题都是区间操作。

        

 

        1. 区间修改用数组数组维护差分数组

        2. 区间查询,需要log计算两个端点的前缀和。上图右侧,可以得出,计算前缀和需要维护差分序列和  i*b[ i ] 的差分序列。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
ll n,m,a[N],b[N],tr1[N],tr2[N];
int lowbit(int x){
	return x&-x;
}
void add1(int x,ll k){
	for(int i=x;i<=n;i+=lowbit(i)) tr1[i]+=k;
}
void add2(int x,ll k){
	for(int i=x;i<=n;i+=lowbit(i)) tr2[i]+=k;
}
ll sum(int x){
	ll ans=0;
	for(int i=x;i;i-=lowbit(i)) ans+=tr1[i];
	ans*=x+1;
	for(int i=x;i;i-=lowbit(i)) ans-=tr2[i];
	return ans;
}
int main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		b[i]=a[i]-a[i-1];
		add1(i,b[i]);
		add2(i,i*b[i]);
	}
	while(m--){
		char op;
		cin>>op;
		if(op=='C'){
			int l,r,d;
			scanf("%lld%lld%lld",&l,&r,&d);
			add1(l,d);
			add1(r+1,-d);
			add2(l,d*l);
			add2(r+1,-d*(r+1));
		}
		else{
			int x,y;
			scanf("%lld%lld",&x,&y);
			printf("%lld\n",sum(y)-sum(x-1));
		}
	}
	return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/63291.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Spring事务(声明式事务)(Spring的事务,Spring隔离级别,事务传播机制)

目录 一、什么是事务&#xff0c;为什么要用事务 二、Spring声明式事务 &#x1f345; 1、Transactional的使用 &#x1f388; 事务回滚 &#x1f388;注意&#xff1a;异常被捕获&#xff0c;不会发生事务回滚 &#x1f345; 2、Transactional 作⽤范围 &#x1f345; …

跨隔离网文件交换,IT部门和业务部门难以兼顾怎么办?

网络隔离技术作为有效的网络安全和数据安全的管理手段&#xff0c;现在已经被充分运用在企业网络建设中。但企业进行网络隔离是基于安全考虑&#xff0c;被隔离的网络间的数据交换需求不会因网络隔离而消失&#xff0c;因此&#xff0c;企业就需要进行隔离网间的数据和文件交换…

element表格+表单+表单验证结合运用

目录​​​​​​​ 一、结果展示 二、实现代码 一、结果展示 1、图片 2、描述 table中放form表单&#xff0c;放输入框或下拉框或多选框等&#xff1b; 点击添加按钮&#xff0c;首先验证表单&#xff0c;如果存在没填的就验证提醒&#xff0c;都填了就向下添加一行表单表…

力扣:54. 螺旋矩阵(Python3)

题目&#xff1a; 给你一个 m 行 n 列的矩阵 matrix &#xff0c;请按照 顺时针螺旋顺序 &#xff0c;返回矩阵中的所有元素。 来源&#xff1a;力扣&#xff08;LeetCode&#xff09; 链接&#xff1a;力扣 示例&#xff1a; 示例 1&#xff1a; 输入&#xff1a;matrix [[1,…

过滤器和拦截器的六大区别

平时觉得简单的知识点&#xff0c;但通常都不会太关注细节&#xff0c;一旦被别人问起来&#xff0c;反倒说不出个所以然来。真的就是一看就会一说就废。下面带大家一起结合实践来区分过滤器和拦截器吧~ 通俗理解&#xff1a; &#xff08;1&#xff09;过滤器&#xff08;Fil…

vue-cli

vue-cli脚手架 案例一&#xff1a; 案例二&#xff1a; 案例三&#xff1a; ​ 一、脚手架简介 Vue脚手架是Vue官方提供的标准化开发工具&#xff08;开发平台&#xff09;&#xff0c;它提供命令行和UI界面&#xff0c;方便创建vue工程、配置第三方依赖、编译vue工程 1. …

2023年华数杯数学建模C题思路 - 母亲身心健康对婴儿成长的影响

# 1 赛题 C 题 母亲身心健康对婴儿成长的影响 母亲是婴儿生命中最重要的人之一&#xff0c;她不仅为婴儿提供营养物质和身体保护&#xff0c; 还为婴儿提供情感支持和安全感。母亲心理健康状态的不良状况&#xff0c;如抑郁、焦虑、 压力等&#xff0c;可能会对婴儿的认知、情…

Centos更换网卡名称为eth0

Centos更换网卡名称为eth0 已安装好系统后需要修改网卡名称为eth0 编辑配置文件将ens33信息替换为eth0,可在vim命令模式输入%s/ens33/eth0/g替换相关内容 修改内核文件,添加内容:net.ifnames=0 biosdevname=0 [root@nova3 ~]# vim /etc/default/grub 使用命令重新生成g…

VLE基于预训练文本和图像编码器的图像-文本多模态理解模型:支持视觉问答、图文匹配、图片分类、常识推理等

项目设计集合&#xff08;人工智能方向&#xff09;&#xff1a;助力新人快速实战掌握技能、自主完成项目设计升级&#xff0c;提升自身的硬实力&#xff08;不仅限NLP、知识图谱、计算机视觉等领域&#xff09;&#xff1a;汇总有意义的项目设计集合&#xff0c;助力新人快速实…

OBS视频视频人物实时扣图方法(四种方式)

图片擦除一些杂乱图像 参考&#xff1a;https://www.bilibili.com/video/BV1va411G7be https://github.com/Sanster/lama-cleaner第一种&#xff1a;色度键选项 第二种&#xff1a;浏览器建立窗口选项 参考视频&#xff1a;https://www.bilibili.com/video/BV1WS4y1C7QY http…

git报错:Error merging: refusing to merge unrelated histories

碰对了情人&#xff0c;相思一辈子。 打命令&#xff1a;git pull origin master --allow-unrelated-histories 然后等一会 再push 切记不要有冲突的代码 需要改掉~

Redis BigKey案例

面试题&#xff1a; 阿里广告平台&#xff0c;海量数据里查询某一固定前缀的key小红书&#xff0c;你如何生产上限制keys*/flushdb/flushall等危险命令以防止误删误用&#xff1f;美团&#xff0c;MEMORY USAGE命令你用过吗&#xff1f;BigKey问题&#xff0c;多大算big&#…

密码攻击与ADSelfService Plus的保护

密码攻击是当前网络安全面临的严峻挑战之一。黑客通过不断演进的技术手段&#xff0c;试图入侵用户账户&#xff0c;窃取敏感信息&#xff0c;从而对个人和组织造成严重损害。为了应对密码攻击的威胁&#xff0c;ManageEngine推出了ADSelfService Plus&#xff0c;这是一款功能…

Clion开发Stm32之存储模块(W25Q64)驱动编写

前言 涵盖之前文章: Clion开发STM32之HAL库SPI封装(基础库) W25Q64驱动 头文件 #ifndef F1XX_TEMPLATE_MODULE_W25Q64_H #define F1XX_TEMPLATE_MODULE_W25Q64_H#include "sys_core.h" /* Private typedef ---------------------------------------------------…

国联易安网页防篡改保护系统“渠道招募”启动啦!

作为业内专注于保密与非密领域的分级保护、等级保护、业务连续性安全和大数据安全的领军企业&#xff0c;国联易安网页防篡改保护系统基于“高效同步”、“安全传输”两项技术&#xff0c;具备了独特的“五重防护”新特性&#xff0c;支持网页的全自动发布、网页监控、报警和自…

Mybatis-plus动态条件查询QueryWrapper的使用

Mybatis-plus动态条件查询QueryWrapper的使用 一&#xff1a;queryWrapper介绍 queryWrapper是mybatis plus中实现查询的对象封装操作类&#xff0c;可以封装sql对象&#xff0c;包括where条件&#xff0c;order by排序&#xff0c;select哪些字段等等&#xff0c;他的层级关…

Navicat远程连接Linux的MySQL

打开Linux终端&#xff0c;进入root权限&#xff0c;用vim打开MySQL的配置文件 vim /etc/mysql/mysql.conf.d/mysqld.cnf将bind-address的值改为0.0.0.0 进入MySQL mysql -u root -p 将root用户改为允许远程登录 update user set host % where user root; 创建用户 CRE…

uni-app:实现点击按钮出现底部弹窗(uni.showActionSheet+自定义)

一、通过uni.showActionSheet实现底部选择 效果 代码 <template><view><button click"showActionsheet">点击打开弹窗</button></view> </template><script> export default {methods: {showActionsheet() {uni.showAct…

从0开始自学网络安全(黑客)

前言 黑客技能是一项非常复杂和专业的技能&#xff0c;需要广泛的计算机知识和网络安全知识。你可以参考下面一些学习步骤&#xff0c;系统自学网络安全。 在学习之前&#xff0c;要给自己定一个目标或者思考一下要达到一个什么样的水平&#xff0c;是学完找工作&#xff08;…

51单片机学习--DS18B20温度读取温度报警器

需要先编写OneWire模块&#xff0c;再在DS18B20模块中调用OneWire模块的函数 先根据原理图做好端口的声明&#xff1a; sbit OneWire_DQ P3^7;接下来像之前一样把时序结构用代码模拟出来&#xff1a; unsigned char OneWire_Init(void) {unsigned char i;unsigned char Ac…