线段树练习

1.单点修改+区间查询

P3374 【模板】树状数组 1

题目描述

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

  • 将某一个数加上 x

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

输入格式

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

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

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

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

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

输出格式

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

输入输出样例

输入 #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% 的数据，1≤n≤8，1≤m≤10；
对于 70% 的数据，1≤n,m≤10^4；
对于 100% 的数据，1≤n,m≤5×10^5。

数据保证对于任意时刻，a 的任意子区间（包括长度为 1 和 n 的子区间）和均在 [−231,231) 范围内。

样例说明：

故输出结果14、16

解题思路

单点修改操作：递归到叶子结点，然后对叶子结点进行修改，然后返回的时候又改变其父节点

void find(int p, int x, int k)
{
	if (a[p].l == a[p].r)//到叶子结点，直接修改
	{
		a[p].data += k;
		return;
	}
	if (x <= a[2 * p].r)
		find(2 * p, x, k);
	else
		find(2 * p + 1, x, k);
	//回溯修改父类结点
	a[p].data = a[2 * p].data + a[2 * p + 1].data;
}

 区间查询：当递归调用的区间完全在查询的区间里面，直接返回对应的值,节约时间,当递归区间没有在查询的区间内直接返回0，当有部分区间在查询区间里面直接返回

int modify(int p, int l, int r)
{
	if (a[p].l >= l && a[p].r <= r) //完全在查询区间里面
	{
		return a[p].data;
	}
	if (a[p].r<l || a[p].l>r) //完全不在查询区间里面
		return 0;
	int an = 0;
	部分在查询区间里面
	if (l <= a[2 * p].r)
		an += modify(p * 2, l, r);
	if (r >= a[2 * p + 1].l)
		an += modify(p * 2 + 1, l, r);
	return an;
}

完整代码

#include<stdio.h>
int n, m;
struct nnn {
	int data;
	int l, r;
}a[2000010];
int b[500010], ans;
//建树
void dfs(int x,int l,int r)
{
	a[x].l = l; a[x].r = r;
	if (l == r)//叶子结点赋值
	{
		a[x].data = b[l];
		return;
	}
	int mid = (l + r) / 2;
	dfs(2 * x,l,mid);
	dfs(2 * x + 1, mid + 1, r);
	a[x].data = a[2 * x].data + a[2 * x + 1].data;
}
//区间查询
int modify(int p, int l, int r)
{
	if (a[p].l >= l && a[p].r <= r) //完全在查询区间里面
	{
		return a[p].data;
	}
	if (a[p].r<l || a[p].l>r) //完全不在查询区间里面
		return 0;
	int an = 0;
	部分在查询区间里面
	if (l <= a[2 * p].r)
		an += modify(p * 2, l, r);
	if (r >= a[2 * p + 1].l)
		an += modify(p * 2 + 1, l, r);
	return an;
}
//单点修改
void find(int p, int x, int k)
{
	if (a[p].l == a[p].r)//到叶子结点，直接修改
	{
		a[p].data += k;
		return;
	}
	if (x <= a[2 * p].r)
		find(2 * p, x, k);
	else
		find(2 * p + 1, x, k);
	//回溯修改父类结点
	a[p].data = a[2 * p].data + a[2 * p + 1].data;
}
int main()
{
	int c, u, v, k;
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++)
		scanf("%d", &b[i]);
	dfs(1, 1, n);
	while (m--)
	{
		scanf("%d %d %d", &c, &v, &k);
		if (c == 1)
			find(1, v, k);
		else
		{
			ans = modify(1, v, k);
			printf("%d\n", ans);
		}
	}
	return 0;
}

2.区间修改+单点查询

P3368 【模板】树状数组 2

题目描述

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

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

  2. 求出某一个数的值。

输入格式

第一行包含两个整数 N、M，分别表示该数列数字的个数和操作的总个数。

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

接下来 M 行每行包含 2 或 4个整数，表示一个操作，具体如下：

操作 1： 格式：1 x y k 含义：将区间 [x,y] 内每个数加上 k；

操作 2： 格式：2 x 含义：输出第 x 个数的值。

输出格式

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

输入输出样例

输入 #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% 的数据：8N≤8，M≤10；

对于 70% 的数据：N≤10000，M≤10000；

对于 100% 的数据：1≤N,M≤500000，1≤x,y≤n，保证任意时刻序列中任意元素的绝对值都不大于 2^30。

解题思路

基本操作和上面一样，修改与查询改一下就可以了

完整代码

#include<stdio.h>
int n, m;
struct nnn {
	int data;
	int l, r;
}a[2000010];
int b[500010], ans;
//建树
void dfs(int x,int l,int r)
{
	a[x].l = l; a[x].r = r; a[x].data = 0;
	if (l == r)
	{
		a[x].data = b[l];
		return;
	}
	int mid = (l + r) / 2;
	dfs(2 * x,l,mid);
	dfs(2 * x + 1, mid + 1, r);
	//a[x].data = a[2 * x].data + a[2 * x + 1].data;
}
//区间修改
void modify(int p, int l, int r, int k)
{
	if (a[p].l >= l && a[p].r <= r) {
		a[p].data += k;
		return;
	}
	int mid = (a[p].l + a[p].r) /2 ;
	if (l <= mid)
		modify(p *2 , l, r, k);
	if (r > mid)
		modify(p *2 + 1, l, r, k);
}
//单点查询
void find(int p, int x)
{
	ans += a[p].data;
	if (a[p].l == a[p].r) return;
	int mid = (a[p].l + a[p].r) / 2;
	if (x <= mid)
		find(2 * p, x);
	else
		find(2 * p + 1, x);
}
int main()
{
	int c, u, v, k;
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++)
		scanf("%d", &b[i]);
	dfs(1, 1, n);
	while (m--)
	{
		scanf("%d", &c);
		if (c == 1)
		{
			scanf("%d %d %d", &u, &v, &k);
			modify(1, u, v, k);
		}
		else
		{
			ans = 0;
			int d;
			scanf("%d", &d);
			find(1, d);
			printf("%d\n", ans);
		}
	}
	return 0;
}

3(区间修改+区间查询)

P3372 【模板】线段树 1

题目描述

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

  1. 将某区间每一个数加上 k。
  2. 求出某区间每一个数的和。

输入格式

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

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

接下来 m 行每行包含 3 或 4 个整数，表示一个操作，具体如下：

  1. 1 x y k：将区间 [x,y] 内每个数加上 k。
  2. 2 x y：输出区间 [x,y] 内每个数的和。

输出格式

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

输入输出样例

输入 #1

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

输出 #1

11
8
20

说明/提示

对于 30% 的数据：n≤8，m≤10。
对于 70% 的数据：n≤10^3，m≤10^4。
对于 100% 的数据：1≤n,m≤10^5。

保证任意时刻数列中所有元素的绝对值之和 ≤1018≤1018。

【样例解释】

 解题思路

这里并不是把前面两种结合一下就可以了，需要用一个懒标记记录需要向下传多少给儿子

向下传的代码

void push_down(long long p)
{
	if (a[p].lz != 0)
	{
		a[p * 2].lz += a[p].lz;//左右儿子分别加上父亲的lz
		a[p * 2 + 1].lz += a[p].lz;
		long long mid = (a[p].l + a[p].r) / 2;
		a[2 * p].data += a[p].lz * (mid - a[2 * p].l + 1);
		a[2 * p + 1].data += a[p].lz * (a[2 * p + 1].r - mid);
		a[p].lz = 0;
	}
}

完整代码

#include<stdio.h>
long long n, m;
struct nnn {
	long long data;
	long long l, r, lz;
}a[2000010];
long long b[500010], ans;
//建树
void dfs(long long x, long long l, long long r)
{
	a[x].l = l; a[x].r = r;
	if (l == r)
	{
		a[x].data = b[l];
		return;
	}
	long long mid = (l + r) / 2;
	dfs(2 * x, l, mid);
	dfs(2 * x + 1, mid + 1, r);
	a[x].data = a[2 * x].data + a[2 * x + 1].data;
}
void push_down(long long p)
{
	if (a[p].lz != 0)
	{
		a[p * 2].lz += a[p].lz;//左右儿子分别加上父亲的lz
		a[p * 2 + 1].lz += a[p].lz;
		long long mid = (a[p].l + a[p].r) / 2;
		a[2 * p].data += a[p].lz * (mid - a[2 * p].l + 1);
		a[2 * p + 1].data += a[p].lz * (a[2 * p + 1].r - mid);
		a[p].lz = 0;
	}
}
void modify(long long p, long long l, long long r, long long k)
{
	if (a[p].l >= l && a[p].r <= r) {
		a[p].data += k * (a[p].r - a[p].l + 1);
		a[p].lz += k;
		return;
	}
	push_down(p);
	long long mid = (a[p].l + a[p].r) / 2;
	if (l <= mid)
		modify(p * 2, l, r, k);
	if (r > mid)
		modify(p * 2 + 1, l, r, k);
	a[p].data = a[p * 2].data + a[p * 2 + 1].data;
}
long long find(long long p, long long l, long long r)
{
	if (a[p].l >= l && a[p].r <= r) {
		return a[p].data;
	}
	if (a[p].r<l || a[p].l>r)
		return 0;
	push_down(p);
	long long an = 0;
	if (l <= a[2 * p].r)
		an += find(p * 2, l, r);
	if (r >= a[2 * p + 1].l)
		an += find(p * 2 + 1, l, r);
	return an;
}
int main()
{
	int c;
	long long u, v, k;
	scanf("%lld %lld", &n, &m);
	for (int i = 1; i <= n; i++)
		scanf("%lld", &b[i]);
	dfs(1, 1, n);
	while (m--)
	{
		scanf("%d", &c);
		if (c == 1)
		{
			scanf("%lld %lld %lld", &u, &v, &k);
			modify(1, u, v, k);
		}
		else
		{
			scanf("%lld %lld", &u, &v);
			ans = find(1, u, v);
			printf("%lld\n", ans);
		}
	}
	return 0;
}

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

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

相关文章

x86汇编写矩阵乘法问题（实现一个3×3矩阵乘法的汇编代码）

x86汇编写矩阵乘法问题（实现一个3×3矩阵乘法的汇编代码）

&#x1f3c6;本文收录于「Bug调优」专栏&#xff0c;主要记录项目实战过程中的Bug之前因后果及提供真实有效的解决方案&#xff0c;希望能够助你一臂之力&#xff0c;帮你早日登顶实现财富自由&#x1f680;&#xff1b;同时&#xff0c;欢迎大家关注&&收藏&&…
阅读更多...
c++的学习之路：10、string（2）

c++的学习之路：10、string（2）

本章主要说一下模拟实现string类的部分功能&#xff0c;文章末附上所有代码。 目录 一、构造函数与析构函数 二、拷贝构造 三、c_str 四、【】和迭代器的遍历与访问 五、size 六、判断 七、reserve 八、push_back 九、resize 十、append 十一、 十二、insert 十…
阅读更多...
单例(Singleton)设计模式

单例(Singleton)设计模式

2.1 设计模式概述 设计模式是在大量的实践中总结和理论化之后优选的代码结构、编程风格、以及解决问题的思考方式。设计模式免去我们自己再思考和摸索。就像是经典的棋谱&#xff0c;不同的棋局&#xff0c;我们用不同的棋谱。"套路" 经典的设计模式共有23种。每个…
阅读更多...
linux基础篇：linux挂载本地yum源——centos7.9为例

linux基础篇：linux挂载本地yum源——centos7.9为例

linux挂载本地yum源——centos7.9为例 一、Linux本地yum源介绍 Linux本地YUM源是一个本地存储的软件包仓库&#xff0c;它允许用户在不连接互联网的情况下安装、更新和管理软件包。本地YUM源可以提高软件包安装速度&#xff0c;降低网络带宽消耗&#xff0c;并提高软件包管理…
阅读更多...
隐私计算实训营学习七：隐语SCQL的架构详细拆解

隐私计算实训营学习七：隐语SCQL的架构详细拆解

文章目录 一、SCQL Overview1.1 SCQL背景1.2 SCQL Overview 二、SCQL CCL三、SCQL架构 一、SCQL Overview 1.1 SCQL背景 SCQL&#xff1a;属于隐私计算BI范畴&#xff0c;允许多个互不信任参与方在不泄露各自隐私数据的条件下进行联合数据分析。 如下数据在不同机构&#xf…
阅读更多...
【机器学习】如何通过群体智慧解决机器学习的挑战“

【机器学习】如何通过群体智慧解决机器学习的挑战“

机器学习的发展日新月异&#xff0c;但其成功实施的关键之一仍然是获取高质量的、标注良好的数据集。在这篇文章中&#xff0c;我们将探讨如何通过群体智慧来构建和改善机器学习的数据集&#xff0c;尤其是通过reCAPTCHA和带有目的的游戏&#xff08;Games with a Purpose, GWA…
阅读更多...
深度学习-计算机视觉入门-part1

深度学习-计算机视觉入门-part1

计算机视觉入门 文章目录 计算机视觉入门一、 从卷积到卷积神经网络1.图像的基本表示2. 卷积操作3.卷积遇见深度学习3.1 通过学习寻找卷积核3.2 参数共享&#xff1a;卷积带来参数量骤减3.3 稀疏交互&#xff1a;获取更深入的特征 二、手撕卷积代码三、经典CNN模型介绍四、CNN模…
阅读更多...
【一】web框架的本质

【一】web框架的本质

模板文件和静态文件 ​ 模板文件和静态文件是在 web 开发中常用的两种资源文件&#xff0c;用于构建网站和 web 应用。 模板文件&#xff1a;模板文件是用于定义网页结构和内容的文件。 它们通常使用模板引擎&#xff08;例如Jinja2或Django模板&#xff09;来插入动态数据&a…
阅读更多...
【算法练习】28：选择排序学习笔记

【算法练习】28：选择排序学习笔记

一、选择排序的算法思想 弄懂选择排序算法&#xff0c;先得知道两个概念&#xff1a;未排序序列&#xff0c;已排序序列。 原理&#xff1a;以升序为例&#xff0c;选择排序算法的思想是&#xff0c;先将整个序列当做未排序的序列&#xff0c;以序列的第一个元素开始。然后从左…
阅读更多...
scala实现通过Spark统计人均登录次数最终写入MySQL

scala实现通过Spark统计人均登录次数最终写入MySQL

谨以此博客作为记录 小编这里用的版本是&#xff1a; <hadoop.version>2.7.7</hadoop.version> <spark.version>2.4.5</spark.version> <scala.version>2.12.10</scala.version> 如果没用到Hadoop可以忽略 步骤 准备数据&#xff0c;知道…
阅读更多...
【Latex】参考文献标号未对齐解决方案

【Latex】参考文献标号未对齐解决方案

Latex写论文时发现最后参考文献标号出现如下没有对齐的情况&#xff1a; 解决方案&#xff1a; 将参考文献开始出的序号1改为99&#xff08;或者其他大点的数字也可以&#xff09; ⬇⬇⬇⬇⬇⬇⬇⬇⬇⬇⬇⬇⬇⬇⬇⬇⬇⬇⬇⬇⬇⬇⬇⬇⬇⬇⬇⬇⬇⬇⬇⬇⬇⬇⬇⬇⬇⬇⬇⬇⬇⬇⬇⬇
阅读更多...
JSON的定义和基本使用

JSON的定义和基本使用

1、JSON的特点: JSON是一种轻量级的数据交换格式&#xff0c;是由字符串化的键值对构成。基于网络的前后端通信&#xff0c;数据在服务端和客户端之间进行传输&#xff0c;采用的就是JSON的格式来进行交互。JSON采用完全独立于语言的文本格式&#xff0c;JSON的数据格式完全独…
阅读更多...
HarmonyOS（鸿蒙）——单击事件

HarmonyOS（鸿蒙）——单击事件

2.4 实现ClickedListener接口并重写onClick方法 2.5 实现onClick方法中的具体逻辑&#xff0c;以此完成点击事件的相关业务操作 三、测试 3.1 登录远程模拟器 3.2 运行项目 四、精选好文 一、简介 1.1 什么是组件 组件就是文本、按钮、图片等元素的统称 1.2 什么是事件 …
阅读更多...
【测试篇】测试用例

【测试篇】测试用例

文章目录 前言具体设计测试用例等价类边界值场景设计法判定表&#xff08;因果图&#xff09;正交排列&#xff08;用的非常少&#xff09;错误猜测法 前言 什么是测试用例&#xff1f;&#xff1f; 测试用例是针对软件系统或应用程序的特定功能或场景编写的一组步骤&#xf…
阅读更多...
了解 Solidity 语言：构建智能合约的首选编程语言

了解 Solidity 语言：构建智能合约的首选编程语言

了解 Solidity 语言&#xff1a;构建智能合约的首选编程语言 Solidity 是一种用于编写智能合约的高级编程语言&#xff0c;广泛应用于以太坊和其他以太坊虚拟机&#xff08;EVM&#xff09;兼容的区块链平台。它是以太坊智能合约的首选语言之一&#xff0c;具有丰富的功能和灵活…
阅读更多...
GEE教程——如何利用影像行列号和distinct函数实现影像的筛选

GEE教程——如何利用影像行列号和distinct函数实现影像的筛选

如何利用影像行列号和distinct函数实现影像的筛选 本次主要利用Landsat中 WRS_PATH 和 WRS_ROW属性实现对影像的筛选。这里我们会用到遍历函数map也就是我们需要对其影像中的每一景影像的行列号属性进行获取，然后再对其列表化，然后利用distinct函数实现属性分离，最后移除不…
阅读更多...
Coursera上托福专项课程01：TOEFL Reading and Listening Sections Skills Mastery 学习笔记

Coursera上托福专项课程01：TOEFL Reading and Listening Sections Skills Mastery 学习笔记

TOEFL Reading and Listening Sections Skills Mastery Course Certificate 本文是学习 https://www.coursera.org/learn/toefl-reading-listening-sections-skills-mastery 这门课的笔记&#xff0c;如有侵权&#xff0c;请联系删除。 文章目录 TOEFL Reading and Listening …
阅读更多...
【系统架构师】-软件产品线与构件

【系统架构师】-软件产品线与构件

1、产品线 核心资源、产品集合 1、过程驱动 2、特定领域 3、技术支持 4、以架构为中心 双生命周期模型&#xff1a; 建立产品线的方式&#xff1a;演化、革命 成功因素&#xff1a; 对该领域具备长期和深厚的经验 一个用于构建产品的好的核心资源库 好的产品线架构 好的管…
阅读更多...
STM32CubeMX 中配置__weak类型函数和用法

STM32CubeMX 中配置__weak类型函数和用法

目录 概述 1 weak类型函数 1.1 weak类型函数介绍 1.2 weak类型函数的特点 2 在 STM32CubeMX中配置weak类型函数 2.1 配置函数类型 2.2 生成代码 2.3 验证 3 _weak类型函数项目中的应用 3.1 重写_weak类型函数 3.2 测试 4 总结 概述 本文主要介绍__weak类型函数…
阅读更多...
java算法day44 | 动态规划part06 ● 完全背包 ● 518. 零钱兑换 II ● 377. 组合总和 Ⅳ

java算法day44 | 动态规划part06 ● 完全背包 ● 518. 零钱兑换 II ● 377. 组合总和 Ⅳ

完全背包理论基础 完全背包和01背包问题唯一不同的地方就是&#xff0c;每种物品有无限件。 体现在代码中就是对背包的遍历顺序不同。01背包是逆序遍历背包&#xff0c;完全背包是顺序遍历背包。 518. 零钱兑换 II class Solution {public int change(int amount, int[] coin…
阅读更多...
最新文章

Copyright @ 2022~2023