1. Toy模板网首页
  2. > Toy博客

【高级数据结构】线段树

9月前 作者：萌新好菜 分类：Toy博客 阅读(38) 违法举报

这篇具有很好参考价值的文章主要介绍了【高级数据结构】线段树。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

目录

树状数组1（单点修改，区间查询）

树状数组2（区间修改，单点查询）

线段树1（区间修改，区间查询）

代码源线段树1（查询最小值出现次数）

 代码源线段树2（最大字段和）

树状数组1（单点修改，区间查询）

题目链接：  https://www.luogu.com.cn/problem/P3374

代码：文章来源地址https://www.toymoban.com/news/detail-611205.html

// Problem: P3374 【模板】树状数组 1
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3374
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

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

typedef long long ll;

const int N = 5e5+5;

int n,q;
int a[N];

struct node{
	ll t,val,sz,l,r;
}seg[N*4];


void update(int id){
	seg[id].val=seg[id*2].val+seg[id*2+1].val;
}

void settag(int id,ll t){
	seg[id].t=seg[id].t+t;
	seg[id].val=seg[id].val+seg[id].sz*t;
}

void pushdown(int id){
	if(seg[id].t!=0){  
		settag(id*2,seg[id].t);
		settag(id*2+1,seg[id].t);
		seg[id].t=0;
	}
}

void build(int id,int l,int r){
	seg[id].sz=r-l+1;
	if(l==r){
		seg[id].val={a[l]};
	}
	else{
		int mid=(l+r)/2;
		build(id*2,l,mid);
		build(id*2+1,mid+1,r);
		update(id);
	}
}

void change(int id,int l,int r,int pos,ll val){
	if(l==r){
		seg[id].val=seg[id].val+val;
		return;
	}
	int mid=(l+r)/2;
	if(pos<=mid){
		change(id*2,l,mid,pos,val);
	}
	else if(pos>mid){
		change(id*2+1,mid+1,r,pos,val);
	}
	update(id);
}

ll query(int id,int l,int r,int ql,int qr){
	if(ql==l&&qr==r){
		return seg[id].val;
	}
	int mid=(l+r)/2;
	pushdown(id);
	if(qr<=mid){
		return query(id*2,l,mid,ql,qr);
	}
	else if(ql>mid){
		return query(id*2+1,mid+1,r,ql,qr);
	}
	else{
		return query(id*2,l,mid,ql,mid)+query(id*2+1,mid+1,r,mid+1,qr);
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	build(1,1,n);
	for(int i=0;i<q;i++){
		int ty;
		cin>>ty;
		if(ty==1){
			int x,d;
			cin>>x>>d;
			change(1,1,n,x,d);
		}
		else{
			int l,r;
			cin>>l>>r;
			cout<<query(1,1,n,l,r)<<"\n";
		}
	}

	
	return 0;	

}
树状数组2（区间修改，单点查询）

 题目链接：  https://www.luogu.com.cn/problem/P3368

代码：

// Problem: P3372 【模板】线段树 1
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3372
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

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

typedef long long ll;

const int N = 5e5+5;

int n,q;
int a[N];

struct node{
	ll t,val,sz,l,r;
}seg[N*4];


void update(int id){
	seg[id].val=seg[id*2].val+seg[id*2+1].val;
}

void settag(int id,ll t){
	seg[id].t=seg[id].t+t;
	seg[id].val=seg[id].val+seg[id].sz*t;
}

void pushdown(int id){
	if(seg[id].t!=0){  
		settag(id*2,seg[id].t);
		settag(id*2+1,seg[id].t);
		seg[id].t=0;
	}
}

void build(int id,int l,int r){
	seg[id].sz=r-l+1;
	if(l==r){
		seg[id].val={a[l]};
	}
	else{
		int mid=(l+r)/2;
		build(id*2,l,mid);
		build(id*2+1,mid+1,r);
		update(id);
	}
}

void modify(int id,int l,int r,int ql,int qr,ll t){
	if(l==ql&&r==qr){
		settag(id,t);
		return;
	}
	int mid=(l+r)/2;
	pushdown(id);
	if(qr<=mid){
		modify(id*2,l,mid,ql,qr,t);
	}
	else if(ql>mid){
		modify(id*2+1,mid+1,r,ql,qr,t);
	}
	else{
		modify(id*2,l,mid,ql,mid,t);
		modify(id*2+1,mid+1,r,mid+1,qr,t);
	}
	update(id);
}

ll query(int id,int l,int r,int pos){
	if(r==l){
		return seg[id].val;
	}
	int mid=(l+r)/2;
	pushdown(id);
	if(pos<=mid){
		return query(id*2,l,mid,pos);
	}
	else if(pos>mid){
		return query(id*2+1,mid+1,r,pos);
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	build(1,1,n);
	for(int i=0;i<q;i++){
		int ty;
		cin>>ty;
		if(ty==1){
			int l,r,d;
			cin>>l>>r>>d;
			modify(1,1,n,l,r,d);
		}
		else{
			int x;
			cin>>x;
			cout<<query(1,1,n,x)<<"\n";
		}
	}

	
	return 0;	

}
线段树1（区间修改，区间查询）

题目链接：  https://www.luogu.com.cn/problem/P3372

代码：

// Problem: P3372 【模板】线段树 1
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3372
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

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

typedef long long ll;

const int N = 2e5+5;

int n,q;
int a[N];

struct node{
	ll t,val,sz;
}seg[N*4];


void update(int id){
	seg[id].val=seg[id*2].val+seg[id*2+1].val;
}

void settag(int id,ll t){
	seg[id].t=seg[id].t+t;
	seg[id].val=seg[id].val+seg[id].sz*t;
}

void pushdown(int id){
	if(seg[id].t!=0){  
		settag(id*2,seg[id].t);
		settag(id*2+1,seg[id].t);
		seg[id].t=0;
	}
}

void build(int id,int l,int r){
	seg[id].sz=r-l+1;
	if(l==r){
		seg[id].val={a[l]};
	}
	else{
		int mid=(l+r)/2;
		build(id*2,l,mid);
		build(id*2+1,mid+1,r);
		update(id);
	}
}

void modify(int id,int l,int r,int ql,int qr,ll t){
	if(l==ql&&r==qr){
		settag(id,t);
		return;
	}
	int mid=(l+r)/2;
	pushdown(id);
	if(qr<=mid){
		modify(id*2,l,mid,ql,qr,t);
	}
	else if(ql>mid){
		modify(id*2+1,mid+1,r,ql,qr,t);
	}
	else{
		modify(id*2,l,mid,ql,mid,t);
		modify(id*2+1,mid+1,r,mid+1,qr,t);
	}
	update(id);
}

ll query(int id,int l,int r,int ql,int qr){
	if(l==ql&&r==qr){
		return seg[id].val;
	}
	int mid=(l+r)/2;
	pushdown(id);
	if(qr<=mid){
		return query(id*2,l,mid,ql,qr);
	}
	else if(ql>mid){
		return query(id*2+1,mid+1,r,ql,qr);
	}
	else{
		return query(id*2,l,mid,ql,mid)+query(id*2+1,mid+1,r,mid+1,qr);
	}
}

int main(){
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	build(1,1,n);
	for(int i=0;i<q;i++){
		int ty;
		cin>>ty;
		if(ty==1){
			int l,r,d;
			cin>>l>>r>>d;
			modify(1,1,n,l,r,d);
		}
		else{
			int l,r;
			cin>>l>>r;
			cout<<query(1,1,n,l,r)<<"\n";
		}
	}

	
	return 0;	

}
代码源线段树1（查询最小值出现次数）

题目链接：  http://oj.daimayuan.top/course/15/problem/654

代码：

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

typedef long long ll;

const int N = 2e5+5;
const int inf = 0x3f3f3f3f;

int n,q;
int a[N];

struct info{
	
};

info operator +(const info &l,const info &r){
	info a;
	a.minv=min(l.minv,r.minv);
	if(l.minv==r.minv){
		a.mincnt=l.mincnt+r.mincnt;
	}
	else if(l.minv<r.minv){
		a.mincnt=l.mincnt;
	}
	else{
		a.mincnt=r.mincnt;
	}
	return a;
}

struct node{
	info val;
}seg[N*4];

void update(int id){
	seg[id].val=seg[id*2].val+seg[id*2+1].val;
}

void build(int id,int l,int r){
	if(l==r){
		seg[id].val={a[l],1};
	}
	else{
		int mid=(l+r)/2;
		build(id*2,l,mid);
		build(id*2+1,mid+1,r);
		update(id);
	}
}

void change(int id,int l,int r,int pos,int val){
	if(l==r){
		seg[id].val={val,1};
		//a[pos]=val;
	}
	else{
		int mid=(l+r)/2;
		if(pos<=mid){
			change(id*2,l,mid,pos,val);
		}
		else{
			change(id*2+1,mid+1,r,pos,val);
		}
		update(id);
	}
}

info query(int id,int l,int r,int ql,int qr){
	if(l==ql&&r==qr){
		return seg[id].val;
	}
	int mid=(l+r)/2;
	if(qr<=mid){
		return query(id*2,l,mid,ql,qr);
	}
	else if(ql>mid){
		return query(id*2+1,mid+1,r,ql,qr);
	}
	else{
		return query(id*2,l,mid,ql,mid)+query(id*2+1,mid+1,r,mid+1,qr);
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	build(1,1,n);
	for(int i=0;i<q;i++){
		int ty;
		cin>>ty;
		if(ty==1){
			int x,d;
			cin>>x>>d;
			change(1,1,n,x,d);
		}
		else{
			int l,r;
			cin>>l>>r;
			auto ans=query(1,1,n,l,r);
			cout<<ans.minv<<' '<<ans.mincnt<<"\n";
		}
	}
	
	
	
	return 0;	

}
 代码源线段树2（最大字段和）

题目链接： 

目录

树状数组1（单点修改，区间查询）

树状数组2（区间修改，单点查询）

线段树1（区间修改，区间查询）

代码源线段树1（查询最小值出现次数）

 代码源线段树2（最大字段和）

代码：

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

typedef long long ll;

const int N = 2e5+5;
const int inf = 0x3f3f3f3f;

int n,q;
int a[N];

struct info{
	ll mss,mpre,msuf,s;
	info(){}
	info(int a):mss(a),mpre(a),msuf(a),s(a){}
};

info operator +(const info &l,const info &r){
	info a;
	a.mss=max({l.mss,r.mss,l.msuf+r.mpre});
	a.mpre=max(l.mpre,l.s+r.mpre);
	a.msuf=max(r.msuf,r.s+l.msuf);
	a.s=l.s+r.s;
	return a;
}

struct node{
	info val;
}seg[N*4];

void update(int id){
	seg[id].val=seg[id*2].val+seg[id*2+1].val;
}

void build(int id,int l,int r){
	if(l==r){
		seg[id].val=info(a[l]);
	}
	else{
		int mid=(l+r)/2;
		build(id*2,l,mid);
		build(id*2+1,mid+1,r);
		update(id);
	}
}

void change(int id,int l,int r,int pos,int val){
	if(l==r){
		seg[id].val=info(val);
		//a[pos]=val;
	}
	else{
		int mid=(l+r)/2;
		if(pos<=mid){
			change(id*2,l,mid,pos,val);
		}
		else{
			change(id*2+1,mid+1,r,pos,val);
		}
		update(id);
	}
}

info query(int id,int l,int r,int ql,int qr){
	if(l==ql&&r==qr){
		return seg[id].val;
	}
	int mid=(l+r)/2;
	if(qr<=mid){
		return query(id*2,l,mid,ql,qr);
	}
	else if(ql>mid){
		return query(id*2+1,mid+1,r,ql,qr);
	}
	else{
		return query(id*2,l,mid,ql,mid)+query(id*2+1,mid+1,r,mid+1,qr);
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	build(1,1,n);
	for(int i=0;i<q;i++){
		int ty;
		cin>>ty;
		if(ty==1){
			int x,d;
			cin>>x>>d;
			change(1,1,n,x,d);
		}
		else{
			int l,r;
			cin>>l>>r;
			auto ans=query(1,1,n,l,r);
			cout<<ans.mss<<"\n";
		}
	}
	
	
	
	return 0;	

}

到了这里，关于【高级数据结构】线段树的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 【算法 & 高级数据结构】树状数组：一种高效的数据结构（二）

    【算法 & 高级数据结构】树状数组：一种高效的数据结构（二）

    🚀 个人主页 ：为梦而生~ 关注我一起学习吧！ 💡 专栏 ：算法题、 基础算法、数据结构~赶紧来学算法吧 💡 往期推荐 ： 【算法基础 数学】快速幂求逆元（逆元、扩展欧几里得定理、小费马定理） 【算法基础】深搜 数据结构各内部排序算法总结对比及动图演示（插入排序

    2024年03月26日
    浏览(82)
  • 数据结构的魔法：高级算法优化实战

    数据结构的魔法：高级算法优化实战

    🎉欢迎来到数据结构学习专栏~数据结构的魔法：高级算法优化实战 ☆* o(≧▽≦)o *☆嗨~我是IT·陈寒🍹 ✨博客主页：IT·陈寒的博客 🎈该系列文章专栏：数据结构学习 📜其他专栏：Java学习路线 Java面试技巧 Java实战项目 AIGC人工智能 数据结构学习 🍹文章作者技术和水平有

    2024年02月06日
    浏览(43)
  • 【Java数据结构与算法】Day2-高级排序（希尔、归并、快速、计数）

    【Java数据结构与算法】Day2-高级排序（希尔、归并、快速、计数）

    ✅作者简介：热爱Java后端开发的一名学习者，大家可以跟我一起讨论各种问题喔。 🍎个人主页：Hhzzy99 🍊个人信条：坚持就是胜利！ 💞当前专栏：【Java数据结构与算法】 🥭本文内容：Java数据结构与算法中的比较高级的排序，希尔排序、归并排序、快速排序、计数排序

    2024年02月02日
    浏览(62)
  • 高级数据结构与算法 | 布谷鸟过滤器（Cuckoo Filter）：原理、实现、LSM Tree 优化

    高级数据结构与算法 | 布谷鸟过滤器（Cuckoo Filter）：原理、实现、LSM Tree 优化

    如果对布隆过滤器不太了解，可以看看往期博客：海量数据处理（一） ：位图与布隆过滤器的概念以及实现 布隆过滤器 局限 对于需要处理海量数据的时候，如果我们需要快速判断一条记录是否，通常会使用过滤器来进行验证，而其中最常见的就是布隆过滤器（Bloom Filter）—

    2024年02月19日
    浏览(49)
  • 【夜深人静学习数据结构与算法 | 第六篇】贪心算法

    【夜深人静学习数据结构与算法 | 第六篇】贪心算法

    目录 前言： 引入: 贪心算法：     455. 分发饼干 - 力扣（LeetCode） 376. 摆动序列 - 力扣（LeetCode） 53. 最大子数组和 - 力扣（LeetCode） 122. 买卖股票的最佳时机 II - 力扣（LeetCode）         在本文我们将为大家介绍在计算机中比较常见的一种算法：贪心算法。他并没有具体的代

    2024年02月09日
    浏览(47)
  • 数据结构与算法学习（day1）

    数据结构与算法学习（day1）

    （1）我是一个大三的学生（准确来说应该是准大三，因为明天才报名哈哈哈）。 （2）最近就想每天闲着没事也刷些C语言习题来锻炼下编程水平，也一直在思考企业对应届大学生能力的要求，所以经常会想到关于面试的事情。由于我也没实习过，所以我对面试没有一个具象化

    2024年02月10日
    浏览(49)

  • 学习数据结构和算法的第9天

    移除元素 ​ 给你一个数组 nums 和一个值 val ，你需要 原地 移除所有数值等于 val的元素，并返回移除后数组的新长度。 ​ 不要使用额外的数组空间，你必须仅使用 0(1)额外空间并 原地 修改输入数组。 ​ 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

    2024年02月21日
    浏览(37)

  • 学习数据结构和算法的第8天

    进行头插 eg:在数组 1 2 3 4 5的开头插入-1 变成-1 1 2 3 4 5 头删 eg：数组1 2 3 4 5 删去1

    2024年02月22日
    浏览(33)

  • 【学习笔记】数据结构算法文档（类C语言）

    1.1.1 线性表的顺序存储表示 1.1.2 顺序表中基本操作的实现 1.1.2.1 初始化 1.1.2.2 取值 1.1.2.3 查找 1.1.2.4 插入 1.1.2.5 删除 1.1.2.6 计数 1.2.1 单链表的定义和表示 ★ 关于结点 1.2.2 单链表基本操作的实现 1.2.2.1 初始化 1.2.2.2 取值 1.2.2.3 查找 1.2.2.4 插入 1.2.2.5 删除 1.2.2.6 前插法创建单

    2024年02月07日
    浏览(42)
  • 【一起学习数据结构与算法】优先级队列(堆)

    【一起学习数据结构与算法】优先级队列(堆)

    如果我们给每个元素都分配一个数字来标记其优先级，不妨设较小的数字具有较高的优先级，这样我们就可以在一个集合中访问优先级最高的元素并对其进行查找和删除操作了。这样，我们就引入了 优先级队列 这种数据结构。 优先级队列（priority queue） 是0个或多个元素的集

    2024年01月19日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包