526互联

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

发布时间 2023-12-10 15:42:11作者: cn是大帅哥886
其他
 
 
 
简介
线段树(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

 

 

样例解释

无

 

 

暂无