首页 > 其他分享 >2020年初一初二集训队（线段树） 基本操作

2020年初一初二集训队（线段树） 基本操作

时间：2023-12-10 15:44:07浏览次数：36  
标签：年初一 cur rs int 线段 tree 2020 ls 基本操作

其他 线段树详解与实现 - 知乎⁤ (zhihu.com) 线段树 - OI Wiki (oi-wiki.org)   线段树 学习笔记 - xujindong 的博客 - 洛谷博客 (luogu.com.cn)     简介 线段树(segment tree)是一种二叉搜索树，也是平衡二叉树，它的每一个结点对应一个区间[L,R],叶 子结点对应的区间只有一个结点(L=R)。每一个非叶子结点[L,R],其左孩子区间为[L,(L+R)/2],右孩子区间为 [(L+R)/2+1,R]  

 

线段树擅长解决动态/静态 RMQ 和动态/静态 RSQ 问题，其支持单点更新、区间更新、区间最值查 询以及区间和查询，且操作效率均和 logn 有关。     线段树的存储 以 RMQ 问题为例： 线段树节点要维护三个信息：区间左端点 l,区间右端点 r,区间最值 mx，每个树节点可以使用数组进行 存储，用数组模拟静态链表的方式我们在数据结构与算法[基础篇]的二叉搜索树部分已经实现过了。 注意：原始数据规模如果为 MAXN，则线段树的数组存储空间需要开 4*MAXN。   线段树的性能分析 线段树采用了分治算法策略，其点更新、区间更新、区间查询均可以在 O(logn)时间内完成。树状数 组和线段树都用于频繁地修改和查询的问题，树状数组可以实现点更新、区间查询，而线段树还可以实现 区间更新、区间查询。线段树的用途更广，更灵活，树状数组比线段树节省空间，代码简单易懂，但是线 段树更灵活，凡是能用树状数组的问题一定能用线段树。ST 表由于只能解决静态 RMQ 问题，所以对于动 态 RMQ 问题，我们也需要借助线段树求解。     线段树实战 区间和 ybt 1547：【 例 1】区间和 区间更新 ybt 1548：【例 2】A Simple Problem with Integers       基本操作     第1题     建树（线段树基本操作） 查看测评数据信息

有N个整数，对这N个整数构造一颗线段树，每个结点用一个sum保留所代表区间的和。

建树后按照后续遍历，输出各个结点的sum。

输入格式

 

第一行，一个整数N。 1 <= N <= 100000。

 第二行，N整数。每个整数范围[1,10^6]。

 

 

输出格式

 

 一行， 若干个整数。

 

输入/输出例子1

输入：

5

3 6 8 2 9

 

 

输出：

3 6 9 8 17 2 9 11 28

 

 

样例解释

 

根结点1号结点，区间范围是[1,5]共5个结点，递归根结点的左子树，递归根结点的右子树。

 

 

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

const int N=100005;
struct treeNode
{
	int l, r;
	long long sum;
}tree[N<<2];
int n;
long long a[N]; 
void build_stree(int cur, int l, int r)
{
	tree[cur].l=l, tree[cur].r=r;
	if (l==r)
	{
		tree[cur].sum=a[l];
		return;
	}
	int mid=l+r>>1, ls=cur*2, rs=cur*2+1;
	build_stree(ls, l, mid);
	build_stree(rs, mid+1, r);
	
	tree[cur].sum=tree[ls].sum+tree[rs].sum;
}
void dfs(int cur, int l, int r)
{
	if (l==r)
	{
		printf("%lld ", tree[cur].sum);
		return;
	}
	int mid=tree[cur].l+tree[cur].r>>1, ls=cur*2, rs=cur*2+1;
	dfs(ls, l, mid);
	dfs(rs, mid+1, r);
	printf("%lld ", tree[cur].sum);
}
int main() 
{
	scanf("%d", &n);
	for (int i=1; i<=n; i++) scanf("%lld", &a[i]);
	
	build_stree(1, 1, n);
	dfs(1, 1, n);
	return 0;
}

　　

 

 

第2题     无修改查询区间（线段树基本操作） 查看测评数据信息

有N个整数，对这N个整数构造一颗线段树，每个结点用一个sum保留所代表区间的和。

有Q个询问，第i个询问给出s[i]和t[i]，表示询问第s[i]个数至第t[i]个数的总和。

输入格式

 

第一行，N和Q。 1 <= N, Q <= 100000。

第二行，N个整数，每个整数范围[1,10^6]。

接下来有Q行，第i行是s[i]和t[i]。

 

 

输出格式

 

共Q行，每行一个整数。

 

输入/输出例子1

输入：

5 2

3 6 8 2 9

2 4

3 5

 

 

输出：

16

19

 

 

 

样例解释

 

本题纯粹是为了入门，请不要用部分和做。

 

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=100100;

struct treeNode
{
	int l, r;
	LL sum;
}tree[N<<2];
int n, q, x, y;
LL a[N]; 
void build_stree(int cur, int l, int r)
{
	tree[cur].l=l, tree[cur].r=r;
	if (l==r)
	{
		tree[cur].sum=a[l];
		return;
	}
	int mid=l+r>>1, ls=cur*2, rs=cur*2+1;
	build_stree(ls, l, mid);
	build_stree(rs, mid+1, r);
	
	tree[cur].sum=tree[ls].sum+tree[rs].sum;
}
LL query(int cur, int l, int r)
{
	if (l<=tree[cur].l && tree[cur].r<=r) return tree[cur].sum;
	
	int mid=tree[cur].l+tree[cur].r>>1, ls=cur*2, rs=cur*2+1;
	LL sum1=0, sum2=0;
	if (l<=mid) sum1=query(ls, l, r);
	if (r>=mid+1) sum2=query(rs, l, r);
	
	return sum1+sum2;
}
int main() 
{
	scanf("%d%d", &n, &q);
	for (int i=1; i<=n; i++) scanf("%lld", &a[i]);
	
	build_stree(1, 1, n);
	while (q--)
	{
		scanf("%d%d", &x, &y);
		if (x>y) swap(x, y);
		printf("%lld\n", query(1, x, y));
	}
	return 0;
}

　　

 

第3题     修改一个查询一段最大值（线段树基本操作） 查看测评数据信息

在N（1<=N<=100000）个数A1…An组成的序列上进行M(1<=M<=100000)次操作，操作有两种：

1   x  y：表示修改A[x]为y；

2   x  y：询问x到y之间的最大值。

 

输入格式

 

第一行输入N(1 <= N <= 100000)，表示序列的长度，接下来N行输入原始序列；

接下来一行输入M(1 <= M <= 100000)表示操作的次数，接下来M行，每行为1 x y或2 x y

 

输出格式

 

对于每个操作(2)输出对应的答案。

 

输入/输出例子1

输入：

5

1

2

3

4

5

3

2 1 4

1 3 5

2 2 4

 

 

输出：

4

5

 

 

 

样例解释

 

【限制】

保证序列中的所有的数都在int范围内

 

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=100100;

struct treeNode
{
	int l, r;
	LL mx;
}tree[4*N];
int n, q, w, x, y;
LL a[N]; 
void build_stree(int cur, int l, int r)
{
	tree[cur].l=l, tree[cur].r=r;
	if (l==r)
	{
		tree[cur].mx=a[l];
		return;
	}
	int mid=l+r>>1, ls=cur*2, rs=cur*2+1;
	build_stree(ls, l, mid);
	build_stree(rs, mid+1, r);
	
	tree[cur].mx=max(tree[ls].mx, tree[rs].mx);
}
LL query(int cur, int l, int r)
{
	if (l<=tree[cur].l && tree[cur].r<=r) return tree[cur].mx;
	
	int mid=tree[cur].l+tree[cur].r>>1, ls=cur*2, rs=cur*2+1;
	LL mx1=0, mx2=0;
	if (l<=mid) mx1=query(ls, l, r);
	if (r>=mid+1) mx2=query(rs, l, r);
	
	return max(mx1, mx2);
}
void point_update(int cur, int pos, int val)
{
	if (tree[cur].l==tree[cur].r && tree[cur].l==pos)
	{
		tree[cur].mx=val;
		return;
	}
	int mid=tree[cur].l+tree[cur].r>>1, ls=2*cur, rs=2*cur+1;
	if (pos<=mid) point_update(ls, pos, val);
	else if (pos>=mid+1) point_update(rs, pos, val);
	
	tree[cur].mx=max(tree[ls].mx, tree[rs].mx);
}
int main() 
{
	scanf("%d", &n);
	for (int i=1; i<=n; i++) scanf("%lld", &a[i]);
	scanf("%d", &q);
	
	build_stree(1, 1, n);
	while (q--)
	{
		scanf("%d%d%d", &w, &x, &y);
		//if (x>y) swap(x, y);
		
		if (w==1) point_update(1, x, y);
		else if (w==2) printf("%lld\n", query(1, x, y));
	}
	return 0;
}

　　

第4题     修改一段查询一段最大值（线段树基本操作） 查看测评数据信息

在N（1 <= N <= 100000）个数A1…An组成的序列上进行M(1 <= M <= 100000)次操作，操作有两种：

1 L R C：表示把A[L]到A[R]增加C（C的绝对值不超过10000）；

2 L R：询问A[L]到A[R]之间的最大值。

 

输入格式

 

第一行输入N(1 <= N <= 100000)，表示序列的长度，接下来N行输入原始序列；

接下来一行输入M(1 <= M <= 100000)表示操作的次数，接下来M行，每行为1 L R C或2 L R

 

输出格式

 

对于每个操作(2)输出对应的答案。

 

输入/输出例子1

输入：

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

 

输出：

4
6

 

样例解释

 

【限制】
保证序列中的所有的数都在int范围内

  暂无           第5题     修改一段查询一段总和（线段树基本操作） 查看测评数据信息

在N（1 <= N <= 100000）个数A1…An组成的序列上进行M(1 <= M <= 100000)次操作，操作有两种：

1 L R C：表示把A[L]到A[R]增加C（C的绝对值不超过10000）；

2 L R：询问A[L]到A[R]之间的总和。

 

输入格式

 

第一行输入N(1 <= N <= 100000)，表示序列的长度，接下来N行输入原始序列；

接下来一行输入M(1 <= M <= 100000)表示操作的次数，接下来M行，每行为1 L R C或2 L R

 

输出格式

 

对于每个操作(2)输出对应的答案。

 

输入/输出例子1

输入：

5

1

2

3

4

5

3

2 1 4

1 1 3 3

2 3 5

 

 

输出：

10

15

 

 

样例解释

无

 

 

暂无

标签：年初一,cur,rs,int,线段,tree,2020,ls,基本操作
From： https://www.cnblogs.com/didiao233/p/17892733.html

相关文章

  • [WUSTCTF 2020]（病假回归）
    [WUSTCTF2020]level1下载下来后有俩文件，先看level1查壳，无壳64位，拖入IDA中看到其中的i&1，为按位与运算，取2进制整数i的最低位，如果最低位是1则得1，如果最低位是0则得0。奇数i的最低位是1，偶数i的最低位是0。再看到output文件，里面有198,232,816,200,1536,300,6144,984,5......
  • 实验6熟悉的hive的基本操作
    今天完成了大数据实验六的hive的基本操作参照实验6熟悉Hive的基本操作_hive环境搭建实验报告-CSDN博客、这位博主的代码，但是前期的启动hive并没有按照博主的来，启动hive大家参照我之前的一篇博客来就行我是从黑马教程跟着下载的hiveHIVe的启动以及datagrip配置-王庆园-博客......
  • 2020年高考数学真题一题多解
    (2020理科数学20)已知\(A,B\)为椭圆\(E:\dfrac{x^2}{a^2}+y^2=1(a>1)\)的左右顶点,\(G\)为\(E\)上的上顶点,\(\overrightarrow{AG}\cdot\overrightarrow{GB}=8,P\)为直线\(x=6\)上的动点,\(PA\)与\(E\)的另一个交点为\(C\),\(PB\)与\(C\)的另一交点为\(D\).(1)求\(E\)的方程(2)......
  • 文件的基本操作
    文件的基本操作1.操作文件打开的两种方式#1.文件的操作方式一：#讲文件以指定编码格式打开，讲文件句柄赋值给变量fpfp=open('01.txt','w',encoding='utf-8')#把hello写入文件fp.write("hello")#关闭文件fp.close()2.文件的操作方式二：#Python解释器内置了一个文......
  • MySQL基本操作
    //mysql数据库管理工具简称叫数据库（存放数据，作为动态网站开不可缺少的一环）mysql是一种关系型数据库基本语法：1.查询当前MySQL下有的所有数据库showdatabases;2.创建数据库createdatabase数据库名数据库选项(字符集，校对集)(大部分情况我们都不进行数据选项的设置)......
  • BUUCTF-RE-49-[羊城杯 2020]easyre
    BUUCTF-RE-[羊城杯2020]easyre进入main，简单分析之后进入encode_oneint__cdeclmain(intargc,constchar**argv,constchar**envp){intv3;//eaxintv4;//eaxintv5;//eaxcharStr[48];//[rsp+20h][rbp-60h]BYREFcharStr1[64];//[rsp+50h]......
  • Excel -- 基本操作
    自定义序列导入CSVCtrl+S就不会弹错误了......
  • 2020云计算省赛总结
    前言：本文写于2020/11/2915:25分，写这篇文章的目的有三：1、对专科两年所学做个总结2、让未来能有机会参加竞赛的同学有个参考3、浮躁的社会，需要静下心来思考author：JackSparrowdate：2020/11/292020云计算省赛总结一、私有云部署运维1划分compute磁盘2配置网络、主机名3配置yum......
  • RuCode 2020 Division A+B. I ✖ [PR #5] 和平共处
    前言认认真真学习了一下这道题相关的做法以及有关的二分图网络流理论，感觉自己又刷新了一些东西的理解。所以说我们就从普通的二分图匹配开始吧！二分图匹配众所周知，二分图最大匹配可以用网络流Dinic算法做到\(O(m\sqrtn)\)的复杂度。在某些特定的图下，我们有一种“贪心流”......
  • AutoCAD .NET 二次开发（2020版）找到折线上剩余的顶点
    如果一条折线有两个顶点，已对其中一个顶点应用了圆角，则还剩下一个顶点。 如何通过代码找到这些剩余的顶点（可能不止一个）？可通过遍历所有顶点，判断每个点连接的两边的线是否为直线如果都为直线，则为顶点，不是圆角。代码如下：for(inti=1;i<polyline.NumberOfVertices-1;......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99