竞赛课第六周(树状数组的应用)

实验内容:

HDU 1166 敌兵布阵【线段树】

线段树的应用     敌兵布阵

C国的死对头A国这段时间正在进行军事演习,所以C国间谍头子Derek和他手下Tidy又开始忙乎了。A国在海岸线沿直线布置了N个工兵营地,Derek和Tidy的任务就是要监视这些工兵营地的活动情况。由于采取了某种先进的监测手段,所以每个工兵营地的人数C国都掌握的一清二楚,每个工兵营地的人数都有可能发生变动,可能增加或减少若干人手,但这些都逃不过C国的监视。
中央情报局要研究敌人究竟演习什么战术,所以Tidy要随时向Derek汇报某一段连续的工兵营地一共有多少人,例如Derek问:“Tidy,马上汇报第3个营地到第10个营地共有多少人!”Tidy就要马上开始计算这一段的总人数并汇报。但敌兵营地的人数经常变动,而Derek每次询问的段都不一样,所以Tidy不得不每次都一个一个营地的去数,很快就精疲力尽了,Derek对Tidy的计算速度越来越不满:"你个死肥仔,算得这么慢,我炒你鱿鱼!”Tidy想:“你自己来算算看,这可真是一项累人的工作!我恨不得你炒我鱿鱼呢!”无奈之下,Tidy只好打电话向计算机专家Windbreaker求救,Windbreaker说:“死肥仔,叫你平时做多点acm题和看多点算法书,现在尝到苦果了吧!”Tidy说:"我知错了。。。"但Windbreaker已经挂掉电话了。Tidy很苦恼,这么算他真的会崩溃的,聪明的读者,你能写个程序帮他完成这项工作吗?不过如果你的程序效率不够高的话,Tidy还是会受到Derek的责骂的.

【输入描述】

第一行一个整数T,表示有T组数据。
每组数据第一行一个正整数N(N<=50000),表示敌人有N个工兵营地,接下来有N个正整数,第i个正整数ai代表第i个工兵营地里开始时有ai个人(1<=ai<=50)。
接下来每行有一条命令,命令有4种形式:
(1) Add i j,i和j为正整数,表示第i个营地增加j个人(j不超过30)
(2)Sub i j ,i和j为正整数,表示第i个营地减少j个人(j不超过30);
(3)Query i j ,i和j为正整数,i<=j,表示询问第i到第j个营地的总人数;
(4)End 表示结束,这条命令在每组数据最后出现;
每组数据最多有40000条命令

【输出描述】

对第i组数据,首先输出“Case i:”和回车,
对于每个Query询问,输出一个整数并回车,表示询问的段中的总人数,这个数保持在int以内。

【样例输入】

1

10

1 2 3 4 5 6 7 8 9 10

Query 1 3

Add 3 6

Query 2 7

Sub 10 2

Add 6 3

Query 3 10

End

【样例输出】

6

33

59

【参考代码】

使用了树状数组,没有使用线段树

#include <bits/stdc++.h>
using namespace std;

const int N = 50001;
int people[N], tree[N], ans[N];
#define lowbit(x) ((x) & -(x))
int n;

void add(int x, int d)
{
	while(x <= n)
	{
		tree[x] += d;
		x += lowbit(x);
	}
}

int sum(int x)
{
	int sum = 0;
	while(x > 0)
	{
		sum += tree[x];
		x -= lowbit(x);
	}
	return sum;
}

int findposition(int x) //二分查找
{
	return lower_bound(tree+1, tree+1+N, x) - (tree + 1);
}
/*
1
10
1 2 3 4 5 6 7 8 9 10
Query 1 3
Add 3 6
Query 2 7
Sub 10 2
Add 6 3
Query 3 10
End
*/

int main()
{
	string s;
	int t, temporary1, temporary2;
	cin>>t;
	for(int i=1; i<=t; i++)
	{
		cout << "Case " << i << ':' << endl;
		
		cin>>n;
		for(int j=1; j<=n; j++)
		{
			cin>>people[j];
			add(j, people[j]); //求和
		}
		while(cin >> s && s != "End")
		{
			cin >> temporary1 >> temporary2;
			if(s == "Query") //询问i到j的总人数
			{ //n-m,f(n)-f(m-1)
				int ans1 = sum(temporary1 - 1);
				int ans2 = sum(temporary2);
				cout << ans2 - ans1 << endl;
			}
			else if(s == "Add") //第i个基地增加j人
			{
				add(temporary1, temporary2); //更新tree数组
			}
			else //第i个基地减少j人
			{
				add(temporary1, -temporary2); //更新tree数组
			}
		}	
	}
}

放两张图,不然看不懂

tree数组的值 

2)tree[]数组的更新
        更改ax,那么和它相关的tree[]都会变化。例如改变a3,那么tree[3]、tree[4]、tree[8]
等都会改变。同样,这个计算也利用了lowbit(x)。
        首先更改 tree[3];
        然后3+lowbit(3)=4,更改tree[4];
        接着 4+lowbit(4)'=8,更改tree[8];
        继续,直到最后的tree[n]。
        编程细节见函数add(),复杂度也是O(log2n)。add()函数也用于tree[]的初始化过程: tree[]初始化为0,然后用add()逐一处理 a1,a2,…,an。

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

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

相关文章

批量发送朋友圈还能自动同步朋友圈

现在不管是做服装店、水果店、化妆店、影楼、二手车房等各行各业来说&#xff0c;每天必不可少的就是发各种朋友圈&#xff0c;量大号又多还占手机内存&#xff0c;真!的!很!累! 没有人能拒绝一键转发带来的方便&#xff0c;有了它发朋友圈只需要点一下就复制到了你自己的朋友圈…

tkinter窗口

简单的窗口程序 导入所需的库 from tkinter import * import json 创建一个主窗口 app Tk() 设置窗口大小为 1048x2048 app.geometry(“1048x2048”) 设置窗口背景为灰色 app.configure(bg“gray”) 创建一个 Label 对象&#xff0c;显示 “账号&#xff1a;” 和红色…

finalshell连接VM虚拟机报错,java,net.ConnectException: Connection timed out: connect

适用于&#xff0c;所有第三方连接虚拟机报错。 java,net.ConnectException: Connection timed out: connect Xshell啊什么的。 解决方法&#xff1a; 首先&#xff0c;我想确认一下是否已经安装了finalshell软件并且要连接的CentOS 7服务器已经设置好了。连接不上的问题有很…

二叉树-认识树及堆,堆的实现

一、树的概念及结构 &#xff08;一&#xff09;树的概念 树是一种非线性的数据结构&#xff0c;是n(n≥0)个结点的有限集。当n0时&#xff0c;称为空树。在任意一颗非空树中应满足&#xff1a; 有且仅有一个特殊的结点&#xff0c;称为根结点&#xff0c;根节点没有前驱结点…

STM32F407+DHT11采集数据

1、DHT11简介 DHT11 与单片机之间能采用简单的单总线进行通信&#xff0c;仅仅需要一个 I/O 口。传感器内部湿度和温度数据 40Bit 的数据一次性传给单片机&#xff0c;数据采用校验和方式进行校验&#xff0c;有效的保证数据传输的准确性。DHT11 功耗很低&#xff0c;5V 电源电…

Java-Doc

Java-Doc javdoc命令是用来生成自己的API文档的 参数信息&#xff1a;author作者名version版本号since知名需要最早使用的jdk版本param参数名return返回值情况throws异常抛出情况 1.参数信息的使用&#xff1a; 未完待续... ...

mysql面试题 1

为什么要使用数据库 数据保存在内存 优点&#xff1a; 存取速度快缺点&#xff1a; 数据不能永久保存 数据保存在文件 优点&#xff1a; 数据永久保存缺点&#xff1a;1、速度比内存操作慢&#xff0c;频繁的IO操作。2、查询数据不方便 数据保存在数据库 数据永久保存使用SQL语…

阿里云服务器公网带宽费用全解析(不同计费模式)

阿里云服务器公网带宽怎么收费&#xff1f;北京地域服务器按固定带宽计费一个月23元/M&#xff0c;按使用流量计费0.8元/GB&#xff0c;云服务器地域不同实际带宽价格也不同&#xff0c;阿里云服务器网aliyunfuwuqi.com分享不同带宽计费模式下带宽收费价格表&#xff1a; 公网…

基于SSM+Vue实现的宠物销售系统

基于SSMVue实现的宠物销售系统 系统介绍 系统演示 点击查看视频演示 基于SSMVue实现的宠物销售系统&#xff0c;主要实现的功能有以下几点&#xff1a;管理员&#xff1b;首页、个人中心、宠物分类管理、商品分类管理、宠物用品管理、宠物商店管理、宠物领养管理、用户管理…

【刷题】图论——最小生成树:局域网

要想去除边&#xff0c;并且不改变连通性&#xff0c;而且去除的值最大&#xff0c;相当于保留最小生成树。 注意这题连通块有若干个&#xff0c;所以运行Kruskal相当于形成若干个最小生成树。 如果是prim只能事先处理好各个连通块&#xff0c;然后在连通块内部单独用prim 题目…

vueRouter动态路由(实现菜单权限控制)

一、权限控制管理&#xff1a; 对于企业级的项目, 我们可能需要对项目做权限控制管理, 实现不同角色的用户登录项目根据所拥有的权限访问不同的页面内容&#xff0c;此时就需要使用到动态路由来对权限页面做限制。 【使用vue-router实现动态路由&#xff0c;达到实现菜单权限…

阿里云2核2G服务器这么便宜,能用来做什么?

阿里云2核2G服务器这么便宜&#xff0c;能用来做什么&#xff1f;阿里云2核2G云服务器可以用来搭建网站、爬虫、邮件服务器、接口服务器、个人博客、企业官网、数据库应用、大数据计算、AI人工智能、论坛、电子商务、AI、LLM大语言模型、测试环境等&#xff0c;阿里云2核2G服务…

四、SpringBoot3 整合 Druid 数据源

本章概要 创建程序引入依赖启动类配置文件编写编写 Controller启动测试问题解决 4.1 创建程序 4.2 引入依赖 <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0"xmlns:xsi"http://ww…

解锁电气数据新价值:SolidWorks Electrical助力企业转型

在信息化、数字化的时代&#xff0c;电气数据库已成为企业不可或缺的核心资产。它以其独特的功能和优势&#xff0c;助力企业在激烈的市场竞争中脱颖而出&#xff0c;实现数字化转型的跨越式发展。 SolidWorks Electrical电气数据库具备强大的数据整合能力。它能够将企业内部各…

阿里云服务器带宽价格全解析,附报价单

阿里云服务器公网带宽怎么收费&#xff1f;北京地域服务器按固定带宽计费一个月23元/M&#xff0c;按使用流量计费0.8元/GB&#xff0c;云服务器地域不同实际带宽价格也不同&#xff0c;阿里云服务器网aliyunfuwuqi.com分享不同带宽计费模式下带宽收费价格表&#xff1a; 公网…

【论文研读】Geometric Deep Learning on Molecular Representations

Geometric Deep Learning on Molecular Representationshttps://arxiv.org/pdf/2107.12375.pdf 一、Background 随着网络时代的发展&#xff0c;生活中产生的数据量越来越多&#xff0c;但数据大体分为两类&#xff1a;欧氏数据、非欧氏数据。如图为两类常见的数据&#xff0c…

SpringBoot与MyBatisPlus的依赖版本冲突问题

记录使用SpringBoot和MyBatisPlus时遇到的版本冲突问题解决。 java版本&#xff1a;jdk17 废话&#xff1a;&#xff09;目前在IDEA中使用Spring官方的脚手架最低jdk版本竟然是jdk17了。 当使用SpringBoot3.0版本(3.2.4)&#xff0c;配合使用MP3.5.2版本时报错&#xff1a; Er…

鸿蒙应用开发之富文本(RichText)组件

前面学习了评分组件,现在来学习富文本组件,这个组件用来表示复杂的文本,把文本显示得更加有特色,比如网页一样显示。这种显示会比较复杂,所以应用的场合就会少一点。不过富文本显示最多的,就是即时通讯软件了,比如显示图片与文本,以及一些特殊的字符。 比如显示如下面的…

# Contrastive Learning(对比学习)--CLIP笔记(一)

Contrastive Learning&#xff08;对比学习&#xff09;–CLIP笔记&#xff08;一&#xff09; 参考&#xff1a;CLIP 论文逐段精读【论文精读】_哔哩哔哩_bilibili CLIP简介 CLIP是一种多模态预训练模型&#xff0c;由OpenAI在2021年提出&#xff0c;论文标题&#xff1a;L…

通俗易懂HTTP和HTTPS区别

HTTP&#xff1a;超文本传输协议&#xff0c;它是使用一种明文的方式发送我们的内容&#xff0c;没有任何的加密&#xff0c;例如我们要在网页上输入账号密码&#xff0c;如果使用HTTP协议&#xff0c;账号密码就可能会被暴露&#xff0c;默认端口是80. HTTPS&#xff1a;是HT…