jimore

用户名：uq_30465888842

访问量：9723

签　名：

Don't let the dream just be a dream!!!

等　　级
排　　名	176
经　　验	6841
参赛次数	29
文章发表	63
年　　龄	0
在职情况	学生
学　　校	四川农业大学
专　　业	计算机科学与技术

　　自我简介：

目标院校：上海交通大学

TA的其他文章

二分答案（简单理解）
浏览：446

求一个很大的数的所有质因子（新方法）
浏览：246

佩尔方程——模板题
浏览：221

你可能喜欢

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

C语言程序设计教程（第三版）课后习题11.12 （C语言代码）

线段树题解（简单理解）

　　作者: jimore　　　　发表时间：2022-07-23 16:10:49 浏览：202　|　评论：0　

原题链接：老管家的忠诚2

## 线段树
**一看到单点更改和区间查询就知道用线段树了**
普通线段树模板：
```c++
int num[100005];
struct node
{
	int l,r,w;//l,r代表左右端点，w代表值
}tree[100005*4+1];
 
void build(int l,int r,int k)//构建一颗线段树
{
	tree[k].l=l;
	tree[k].r=r;
	if(l==r)
	{
		tree[k].w=num[l];
		return ;
	}
	int m=(l+r)/2;
	build(l,m,k*2);//左孩子
	build(m+1,r,k*2+1);//右孩子
	tree[k].w=tree[k*2].w+tree[k*2+1].w;//此节点的w等于两个孩子的w之和
}
 
int range_query(int k,int l,int r)
{
	if(l<=tree[k].l&&r>=tree[k].r)
		return tree[k].w;
	if(r<=tree[k*2].r)
		return query(2*k,l,r);
	else if(l>=tree[2*k+1].l)
		return query(2*k+1,l,r);
	else 
		return query(2*k,l,tree[2*k].r)+query(2*k+1,tree[2*k+1].l,r);
}
 
void point_update(int k,int x, int y)
{
	if(tree[k].l==tree[k].r&&tree[k].l==x)//找到目标位置
	{
		tree[k].w=y;
		return;
	}
	else if(tree[2*k].r>=x)
		change(2*k,x,y);
	else
		change(2*k+1,x,y);
	tree[k].w=tree[2*k].w+tree[2*k+1].w;
}
```
在这个题中是求区间最小值，不是区间和，所以就把模板中的`tree[k].w=tree[k*2].w+tree[k*2+1].w`，`return query(2*k,l,tree[2*k].r)+query(2*k+1,tree[2*k+1].l,r)`，`tree[k].w=tree[2*k].w+tree[2*k+1].w`分别改为`tree[k].w=min(tree[k*2].w,tree[k*2+1].w)`，`return min(query(2*k,l,tree[2*k].r),query(2*k+1,tree[2*k+1].l,r))`，`tree[k].w=min(tree[2*k].w,tree[2*k+1].w)`即可。
完整代码：
```c++
#include<iostream>
#include<string>
#include<cstring>
#include<string.h>
#include<algorithm>
using namespace std;
int num[100005];
struct node
{
	int l,r,w;//l,r代表左右端点，w代表值
}tree[100005*4+1];
 
void build(int l,int r,int k)//构建一颗线段树
{
	tree[k].l=l;
	tree[k].r=r;
	if(l==r)
	{
		tree[k].w=num[l];
		return ;
	}
	int m=(l+r)/2;
	build(l,m,k*2);//左孩子
	build(m+1,r,k*2+1);//右孩子
	tree[k].w=min(tree[k*2].w,tree[k*2+1].w);//此节点的w等于两个孩子的w之和
}
 
int query(int k,int l,int r)
{
	if(l<=tree[k].l&&r>=tree[k].r)
		return tree[k].w;
	if(r<=tree[k*2].r)
		return query(2*k,l,r);
	else if(l>=tree[2*k+1].l)
		return query(2*k+1,l,r);
	else 
		return min(query(2*k,l,tree[2*k].r),query(2*k+1,tree[2*k+1].l,r));
}
 
void change(int k,int x, int y)
{
	if(tree[k].l==tree[k].r&&tree[k].l==x)//找到目标位置
	{
		tree[k].w=y;
		return;
	}
	else if(tree[2*k].r>=x)
		change(2*k,x,y);
	else
		change(2*k+1,x,y);
	tree[k].w=min(tree[2*k].w,tree[2*k+1].w);
}
int main()
{
	int i,m,n,p,x,y;
	cin>>m>>n;
	for(int i=1;i<=m;i++)
		cin>>num[i];
	build(1,m,1);
	for(int i=0;i<n;i++)
	{
		cin>>p>>x>>y;
		if(p==1)
			cout<<query(1,x,y)<<" ";
		else if(p==2)
			change(1,x,y);
	}
	return 0;
}
```

0.0分

5 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

jimore

TA的其他文章

你可能喜欢

C语言考试练习题_排列（C++代码）

格式错误一万年，，有没有过了的来看看（终于过了）

P1001 （C++代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

C语言程序设计教程（第三版）课后习题11.12 （C语言代码）

线段树题解（简单理解）

评论区

精彩推荐

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

printf基础练习2 （C语言代码）

打水问题（C语言代码）

C语言训练-大、小写问题（C语言代码）

本人酷爱递归实现很多问题，这里也是

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

数对（C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

图形输出（C语言代码）

jimore

TA的其他文章

你可能喜欢

C语言考试练习题_排列 （C++代码）

格式错误一万年，，有没有过了的来看看（终于过了）

P1001 （C++代码）

C语言程序设计教程（第三版）课后习题10.2 （C语言代码）

C语言程序设计教程（第三版）课后习题11.12 （C语言代码）

线段树题解（简单理解）

评论区

精彩推荐

C语言训练-求矩阵的两对角线上的元素之和 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

printf基础练习2 （C语言代码）

打水问题 （C语言代码）

C语言训练-大、小写问题 （C语言代码）

本人酷爱递归实现很多问题，这里也是

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

数对 （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

图形输出 （C语言代码）

C语言考试练习题_排列（C++代码）

　　评论区

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

打水问题（C语言代码）

C语言训练-大、小写问题（C语言代码）

数对（C语言代码）

图形输出（C语言代码）