每日一题 第六十三期 洛谷 树状数组模板

【模板】树状数组 1

题目描述

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

  • 将某一个数加上 x x x

  • 求出某区间每一个数的和

输入格式

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

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

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

  • 1 x k 含义:将第 x x x 个数加上 k k k

  • 2 x y 含义:输出区间 [ x , y ] [x,y] [x,y] 内每个数的和

输出格式

输出包含若干行整数,即为所有操作 2 2 2 的结果。

样例 #1

样例输入 #1

5 5
1 5 4 2 3
1 1 3
2 2 5
1 3 -1
1 4 2
2 1 4

样例输出 #1

14
16

提示

【数据范围】

对于 30 % 30\% 30% 的数据, 1 ≤ n ≤ 8 1 \le n \le 8 1n8 1 ≤ m ≤ 10 1\le m \le 10 1m10
对于 70 % 70\% 70% 的数据, 1 ≤ n , m ≤ 1 0 4 1\le n,m \le 10^4 1n,m104
对于 100 % 100\% 100% 的数据, 1 ≤ n , m ≤ 5 × 1 0 5 1\le n,m \le 5\times 10^5 1n,m5×105

数据保证对于任意时刻, a a a 的任意子区间(包括长度为 1 1 1 n n n 的子区间)和均在 [ − 2 31 , 2 31 ) [-2^{31}, 2^{31}) [231,231) 范围内。

样例说明:

故输出结果14、16

AC代码:


#include<map>
#include<set>
#include<stack>
#include<cmath>
#include<queue>
#include<string>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<numeric>
#include<iomanip>
#define endl '\n'
//#define x first
//#define y second
using namespace std;

typedef long long ll;
typedef pair<int, int>PII;
const int N=3e5+10;
const int MOD=1e9 + 7;
const int INF=0X3F3F3F3F;
const int dx[]={-1,1,0,0,-1,-1,+1,+1};
const int dy[]={0,0,-1,1,-1,+1,-1,+1};
const int M = 1e6 + 10;

int n, m;
int tree[M];//定义树状数组

int bit(int x)
{
	return x & -x;//x右边第一个
}
void add(int i, int x)
{
	while(i <= n)
	{
		tree[i] += x;
		i += bit(i);
	}
}//要将每一段与i位置有关的树都加上x;
//计算1 到 i的和

ll sum(int i)
{
	ll res = 0;
	while(i > 0){
		res += tree[i];
		i -= bit(i);
	}
	return res;
}
int main()
{
    cin >> n >> m;
	for(int i = 1; i <= n; i ++)
	{
		int x;
		cin >> x;
		add(i, x);// 在第i个位置上加上一个x
	}
	while(m --){
		int a, b, c;
		cin >> a >> b >> c;
		if(a == 1)
		{
			add(b, c);
		}
		if(a == 2)
		{
			cout << sum(c) - sum(b - 1) << endl;
		}
	}
	return 0;
}

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

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

相关文章

4.2 JavaWeb Day05分层解耦

三层架构功能 controller层接收请求&#xff0c;响应数据&#xff0c;层内调用了service层的方法&#xff0c;service层仅负责业务逻辑处理&#xff0c;其中要获取数据&#xff0c;就要去调用dao层&#xff0c;由dao层进行数据访问操作去查询数据&#xff08;进行增删改查&…

YOLOv8结合SCI低光照图像增强算法!让夜晚目标无处遁形!【含端到端推理脚本】

这里的"SCI"代表的并不是论文等级,而是论文采用的方法 — “自校准光照学习” ~ 左侧为SCI模型增强后图片的检测效果,右侧为原始v8n检测效果 这篇文章的主要内容是通过使用SCI模型和YOLOv8进行算法联调,最终实现了如上所示的效果:在增强图像可见度的同时,对图像…

Scala中如何使用Jsoup库处理HTML文档?

在当今互联网时代&#xff0c;数据是互联网应用程序的核心。对于开发者来说&#xff0c;获取并处理数据是日常工作中的重要一环。本文将介绍如何利用Scala中强大的Jsoup库进行网络请求和HTML解析&#xff0c;从而实现爬取京东网站的数据&#xff0c;让我们一起来探索吧&#xf…

【容易不简单】love 2d Lua 俄罗斯方块超详细教程

源码已经更新在CSDN的码库里&#xff1a; git clone https://gitcode.com/funsion/love2d-game.git 一直在找Lua 能快速便捷实现图形界面的软件&#xff0c;找了一堆&#xff0c;终于发现love2d是小而美的原生lua图形界面实现的方式。 并参考相关教程做了一个更详细的&#x…

C++算法——滑动窗口

一、长度最小的子数组 1.链接 209. 长度最小的子数组 - 力扣&#xff08;LeetCode&#xff09; 2.描述 3.思路 本题从暴力求解的方式去切入&#xff0c;逐步优化成“滑动窗口”&#xff0c;首先&#xff0c;暴力枚举出各种组合的话&#xff0c;我们先让一个指针指向第一个&…

【Qt学习笔记 01】Qt 背景介绍

博客主页&#xff1a;Duck Bro 博客主页系列专栏&#xff1a;Qt 专栏关注博主&#xff0c;后期持续更新系列文章如果有错误感谢请大家批评指出&#xff0c;及时修改感谢大家点赞&#x1f44d;收藏⭐评论✍ Qt 背景介绍 文章编号&#xff1a;Qt 学习笔记 / 01 文章目录 Qt 背景…

AttributeError: ‘Namespace‘ object has no attribute ‘EarlyStopping‘

报错原因 这个报错信息表明在Python脚本train.py中尝试访问命令行参数args.EarlyStopping时出错&#xff0c;具体错误是AttributeError: Namespace对象没有名为EarlyStopping的属性。 在Python的argparse模块中&#xff0c;当我们通过命令行传递参数并解析时&#xff0c;解析…

UGUI 进阶

UI事件监听接口 目前所有的控件都只提供了常用的事件监听列表 如果想做一些类似长按&#xff0c;双击&#xff0c;拖拽等功能是无法制作的 或者想让Image和Text&#xff0c;RawImage三大基础控件能够响应玩家输入也是无法制作的 而事件接口就是用来处理类似问题 让所有控件都…

10秒钟用python接入讯飞星火API(保姆级)

正文&#xff1a; 科大讯飞是中国领先的人工智能公众公司&#xff0c;其讯飞星火API为开发者提供了丰富的接口和服务&#xff0c;以支持各种语音和语言技术的应用。 步骤一&#xff1a;注册账号并创建应用 首先&#xff0c;您需要访问科大讯飞开放平台官网&#xff0c;注册一个…

dcoker 下redis设置密码

修改Docker里面Redis密码 Redis是一个开源的内存数据结构存储系统&#xff0c;常用于缓存、消息队列和数据持久化等场景。在使用Docker部署Redis时&#xff0c;默认情况下是没有设置密码的&#xff0c;这可能会导致安全隐患。因此&#xff0c;为了保证数据的安全性&…

2024环境,资源与绿色能源国际会议(ICERGE2024)

2024环境&#xff0c;资源与绿色能源国际会议(ICERGE2024) 会议简介 2024环境、资源与绿色能源国际会议(ICERGE2024)将于2024年在三亚举行。该会议是一个围绕环境、资源与绿色能源研究领域的国际学术交流活动。 会议主题包括但不限于环境科学、环境工程、资源利用、绿色能源开…

微信小程序上传代码到远程仓库

个人介绍 hello hello~ &#xff0c;这里是 code袁~&#x1f496;&#x1f496; &#xff0c;欢迎大家点赞&#x1f973;&#x1f973;关注&#x1f4a5;&#x1f4a5;收藏&#x1f339;&#x1f339;&#x1f339; &#x1f981;作者简介&#xff1a;一名喜欢分享和记录学习的…

MySQL安装卸载

目录 1.概述 2.安装 2.1.安装 2.2.配置 3.卸载 3.1.停服务 3.2.卸载组件 3.3.删除安装目录 3.4.删除数据目录 3.5.检查残留 1.概述 MySQL是一个广受欢迎的关系型数据库管理系统&#xff0c;最初由瑞典的MySQL AB公司开发&#xff0c;现在是Oracle旗下的产品。作为最流…

海外媒体宣发技巧解析从而提升宣发效果

在当今全球化的媒体环境下&#xff0c;海外媒体宣发是企业和品牌推广的重要手段。然而&#xff0c;要在海外市场取得成功&#xff0c;一味地复制国内的宣发策略是行不通的。要想提升宣发效果&#xff0c;就必须了解并掌握一些海外媒体宣发的技巧。世媒讯一家从事海内外媒体的推…

1111111

c语言中的小小白-CSDN博客c语言中的小小白关注算法,c,c语言,贪心算法,链表,mysql,动态规划,后端,线性回归,数据结构,排序算法领域.https://blog.csdn.net/bhbcdxb123?spm1001.2014.3001.5343 给大家分享一句我很喜欢我话&#xff1a; 知不足而奋进&#xff0c;望远山而前行&am…

【中文视觉语言模型+本地部署 】23.08 阿里Qwen-VL:能对图片理解、定位物体、读取文字的视觉语言模型 (推理最低12G显存+)

项目主页&#xff1a;https://github.com/QwenLM/Qwen-VL 通义前问网页在线使用——&#xff08;文本问答&#xff0c;图片理解&#xff0c;文档解析&#xff09;&#xff1a;https://tongyi.aliyun.com/qianwen/ 论文v3. : 一个全能的视觉语言模型 23.10 Qwen-VL: A Versatile…

简直了,被“Java并发锁”问题追问到自闭...

分享是最有效的学习方式。 博客&#xff1a;https://blog.ktdaddy.com/ 故事 地铁上&#xff0c;小帅双目空洞地望着窗外…绝望&#xff0c;发自内心地感到绝望… 距离失业已经过去两个月了&#xff0c;这是小帅接到的第四次面试邀请。“回去等通知吧…”,简简单单的六个字&a…

汽车贴膜改色小程序源码 汽车配色小程序源码 车身改色app源码 带后台 带数据

汽车贴膜改色小程序源码 车身改色app源码 汽车配色小程序源码 带后台 带数据 整站源码&#xff0c;包含完整前端小程序&#xff0c;后台源码&#xff0c;数据库数据。 直接部署&#xff0c;就能使用&#xff0c;源码素材远程开发&#xff0c;可以定制开发。 全开源&#xff0c;…

关于ITIL认证您需要了解的一切

这是一篇关于从业人员、领导者和 ITSM 爱好者指南。ITIL4于2019 年发布。最新版本的 IT 服务管理&#xff08;ITSM&#xff09;最佳实践从传统的生命周期方法转变为服务价值体系模型&#xff0c;重点关注价值共创、向业务交付成果以及与其他最佳实践框架的融合。 新版本的框架…

商城网站-礼品网站首页html+css+js+说明文档

网页设计与网站建设作业htmlcssjs 预览 说明 单页面&#xff0c;轮播图 获取&#xff1a;https://hpc.baicaitang.cn/2077.html