当前位置： 首页 > news >正文

线段树2----简单拓展

news 来源：原创 2024/5/3 5:05:26

通过之前的五个基本操作，可以组合出单点查询，单点修改，区间查询，区间修改等操作。

此外，线段树还可以与其他算法结合

目录

一、维护区间和，最大最小值

二、+差分求区间最大公约数 

三、维护最长连续串 、最大连续子段和……

四、线段树优化dp 

五、+扫描线 

一、维护区间和，最大最小值

243. 一个简单的整数问题2 - AcWing题库 --- 区间和

struct node
{
	int l,r;
	ll sum,add; 
}tr[N*4];

 知道子区间的和即可求出父区间的和，所以对于第二个操作只需要维护一个sum即可，add是懒标记，用来维护区间加操作，父区间的懒标记需要累加到子区间上。

//sum:如果考虑当前节点及子节点的所有标记，当前区间和是多少
//add:给当前区间的所有儿子加上add 
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=100010;
int n,m;
int w[N];
struct node
{
	int l,r;
	ll sum,add; 
}tr[N*4];
void pushup(int u)
{
 	tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
}
void pushdown(int u)
{
 	auto &root=tr[u];
 	auto &left=tr[u<<1];
 	auto &right=tr[u<<1|1];
 	if(root.add)
 	{
 		left.add=left.add+root.add;
 		left.sum=left.sum+ll(left.r-left.l+1)*root.add;
 		right.add+=root.add;
 		right.sum+=ll(right.r-right.l+1)*root.add;
	    root.add=0;
    }
}
void build(int u,int l,int r)
{
 	if(l==r)
 	{
 		tr[u]={l,r,w[r],0};
	}
	else
	{
	    tr[u]={l,r};
	    int mid=l+r>>1;
	    build(u<<1,l,mid),build(u<<1|1,mid+1,r);
		pushup(u); 
	}
}
void modify(int u,int l,int r,int d)
{
	if(tr[u].l>=l&&tr[u].r<=r)
	{
		tr[u].sum+=(ll)(tr[u].r-tr[u].l+1)*d;
		tr[u].add+=d;
	}
	else//一定要分裂 
	{
		pushdown(u);
		int mid=tr[u].l+tr[u].r>>1;
		if(l<=mid)
		modify(u<<1,l,r,d);
		if(r>mid)
		modify(u<<1|1,l,r,d);
		pushup(u);
	}
}
ll query(int u,int l,int r)
{
	if(tr[u].l>=l&&tr[u].r<=r)
	return tr[u].sum;
	pushdown(u);
	int mid=tr[u].l+tr[u].r>>1;
	ll sum=0;
	if(l<=mid)
	sum=query(u<<1,l,r);
	if(r>mid)
	{
		sum+=query(u<<1|1,l,r);
	}
	return sum;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	scanf("%d",&w[i]);
	build(1,1,n);
	char op[2];
	int l,r,d;
	while(m--)
	{
		scanf("%s%d%d",op,&l,&r);
		if(*op=='C')
		{
			scanf("%d",&d);
			modify(1,l,r,d);
		}
		else
		printf("%lld\n",query(1,l,r));
	}
	return 0;
}

二、+差分求区间最大公约数 

246. 区间最大公约数 - AcWing题库

利用更相减损术，可以推得(a,b,c)=(a,b-a,c-b)

那么通过维护差分同样可以求最大公约数，且区间修改可以变为单点修改

struct node
{
	int l,r;
	ll sum;//差分前缀和
	ll d;//最大公约数 
}tr[N*4];
/*此题核心为差分！！！！！！！！！！ */
//l-r同增一个数
/*修改一个数很简单,差分只需要改一个数*/ 
//最大公约数--->只需维护一个公约数--->扩展欧几里得算法
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=500010;
typedef long long ll; 
int n,m;
ll w[N];
struct node
{
	int l,r;
	ll sum;
	ll d;//最大公约数 
}tr[N*4];
ll gcd(ll a,ll b)
{
	return b?gcd(b,a%b):a;
}
void pushup(node &u,node &l,node &r)
{
	u.sum=l.sum+r.sum;
	u.d=gcd(l.d,r.d);
}
void pushup(int u)
{
	pushup(tr[u],tr[u<<1],tr[u<<1|1]);
} 
void modify(int u,int x,ll v)
{
	if(tr[u].l==x&&tr[u].r==x)
	{
		ll b=tr[u].sum+v;
		tr[u]={x,x,b,b};
	}
	else
	{
		int mid=tr[u].l+tr[u].r >> 1;
		if(x<=mid)
		modify(u<<1,x,v);
		else
		modify(u<<1|1,x,v);
		pushup(u);
	}
}
node query(int u,int l,int r)
{
 	if(tr[u].l>=l&&tr[u].r<=r)
 	return tr[u];
 	else
 	{
 		int mid=tr[u].l+tr[u].r>>1;
 		if(r<=mid)
 		return query(u<<1,l,r);
 		else if(l>mid)
 		return query(u<<1|1,l,r);
 		else
 		{
 			auto left=query(u<<1,l,r);
 			auto right=query(u<<1|1,l,r);
 			node res;
 			pushup(res,left,right);
 			return res;
		}
	}
}
void build(int u,int l,int r)//维护差分 
{
	if(l==r)
	{
	 	ll b=w[r]-w[r-1];//维护差分
	 	tr[u]={l,r,b,b};
	}
	else
	{
	 	tr[u].l=l,tr[u].r=r;
	 	int mid=l+r>>1;
	 	build(u<<1,l,mid),build(u<<1|1,mid+1,r);
	 	pushup(u);
	}
} 
int main()
{
 	scanf("%d%d",&n,&m);
 	for(int i=1;i<=n;i++)
 	scanf("%lld",&w[i]);
 	build(1,1,n);
 	int l,r;
 	ll d;
 	char op[2];
 	while(m--)
 	{
 	    scanf("%s%d%d",op,&l,&r);
	    if(*op=='Q')
 	    {
 		    auto left=query(1,1,l);
 	        node right({0,0,0,0});
 	        if(l+1<=r)
 	        right=query(1,l+1,r);
 	        printf("%lld\n",abs(gcd(left.sum,right.d)));
	    }
	    else
	    {
	    	scanf("%lld",&d);
	    	modify(1,l,d);
	    	if(r+1<=n)
	    	modify(1,r+1,-d);
		}
    }
    return 0;
}

三、维护最长连续串 、最大连续子段和……

245. 你能回答这些问题吗 - AcWing题库

维护一个最长连续的子段，对于一个区间来说，最长子段可能是最长前缀，可能是中间的一段，也可能是最长后缀。我们就需要维护这些性质：前缀、后缀，但是只维护这两个信息是不够的，因为最长前缀、最长后缀可能是跨整个子区间的，而前缀是不包含本身的，所以需要再维护一个区间和

struct node
{
	int l,r;
	int tmax;//最大子段和
	int lmax;//最大前缀             
	int rmax;//最大后缀
	int sum;
}tr[N*4];//直到所维护信息具有完备性
//线段树
/*区间内最大子段和=max(完全处于左子区间，完全处于右子区间，横跨左右区间的最大字段和)*/
/*横跨左右子区间的最大字段和=
左子区间的最大后缀+右子区间的最大前缀*/
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=500010;
int n,m;
int w[N]; 
struct node
{
	int l,r;
	int tmax;
	int lmax;               
	int rmax;
	int sum;
}tr[N*4];//直到所维护信息具有完备性 
void pushup(node&u,node&l,node&r)
{
	//第一题中只需计算最大值v，而此题属性较多
	u.sum=l.sum+r.sum;
	u.lmax=max(l.lmax,l.sum+r.lmax);
	u.rmax=max(r.rmax,r.sum+l.rmax);
	u.tmax=max(max(l.tmax,r.tmax),l.rmax+r.lmax); 
}
void pushup(int u)
{
	pushup(tr[u],tr[u<<1],tr[u<<1|1]);
}
void build(int u,int l,int r)
{
	if(l==r)
	tr[u]={l,r,w[r],w[r],w[r],w[r]};
	else
	{
		tr[u]={l,r};
		int mid=l+r>>1;
		build(u<<1,l,mid),build(u<<1|1,mid+1,r);
		pushup(u);
	}
}
void modify(int u,int x,int v)
{
	if(tr[u].l==x&&tr[u].r==x)
	tr[u]={x,x,v,v,v,v};
	else
	{
		int mid=tr[u].l+tr[u].r>>1;
		if(x<=mid)
		modify(u<<1,x,v);
		else
		modify(u<<1|1,x,v);
		pushup(u);
	}
}
node query(int u,int l,int r)
{
	if(tr[u].l>=l&&tr[u].r<=r) return tr[u];
	else
	{
		int mid=tr[u].l+tr[u].r>>1;
		if(r<=mid)
		return query(u<<1,l,r);
		else if(l>mid)
		return query(u<<1|1,l,r);
		else
		{
			auto left=query(u<<1,l,r);
			auto right=query(u<<1|1,l,r);
			node res;
			pushup(res,left,right);
			return res;
		}
	}
} 
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	scanf("%d",&w[i]);
	build(1,1,n);
	int k,x,y;
	while(m--)
	{
		scanf("%d%d%d",&k,&x,&y);
		if(k==1)
		{
			if(x>y)
			swap(x,y);
			printf("%d\n",query(1,x,y).tmax);
		}
		else
		modify(1,x,y);
	}
	return 0;
}

四、线段树优化dp 

295. 清理班次 - AcWing题库 

这道题用贪心可以直接做出来，但可以作为线段树的练习题

我们用dp来解决这道题

状态表示：f[i]表示覆盖前 i 个班次的最小代价

状态转移方程：f[i]=min(f[L-1]+1,f[i])    i\in [L,R]

在每次比较之后f[i]的值都可能会变，所以用线段树维护一下性质最小值

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

typedef long long ll;
const int N = 2500010;
const ll INF = 1e8;

struct seq
{
	int l,r;
	bool operator< (const seq &t) const
	{
		return r < t.r || (r == t.r && l < t.l);
	}
}a[N];

struct node
{
	int l,r;
	ll minv;
}tr[N * 4];
ll f[N];

void pushup(int u)
{
	tr[u].minv = min(tr[u << 1].minv,tr[u <<1|1].minv);
}

void build(int u,int l,int r)
{
	if(l == r)
	tr[u] = {l,r,f[l]};
	else
	{
		tr[u] = {l,r};
		int mid = l + r >> 1;
		build(u << 1,l,mid),build(u<<1|1,mid + 1,r);
		pushup(u);
	}
}

void modify(int u,int x,ll v)
{
	if(tr[u].l == tr[u].r)
	{
		tr[u].minv = v;
		return;
	}
	
	int mid = tr[u].l + tr[u].r >> 1;
	if(x <= mid)
	modify(u<<1,x,v);
	else
	modify(u<<1|1,x,v);
	pushup(u);
} 

ll query(int u,int l,int r)
{
	if(tr[u].l >= l&&tr[u].r <= r)
	return tr[u].minv;
	
	int mid = tr[u].l + tr[u].r >> 1;
	ll res = INF;
	if(l <= mid)
	res = min(res,query(u<<1,l,r));
	if(r>mid)
	res = min(res,query(u<<1|1,l,r));
	return res;
}

int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	
	for(int i = 1; i <= n; i ++)
	{
		scanf("%d%d",&a[i].l,&a[i].r);
		a[i].l = max(a[i].l,1);
		a[i].r = min(a[i].r,m);
	}
	
	sort(a + 1,a + 1 + n);
	
	for(int i = 0; i <= N;i ++)
	f[i] = INF;
	f[0] = 0;
	
	build(1,0,m);
	
	for(int i = 1; i <= n; i ++)
	{
		f[a[i].r] = min(f[a[i].r],query(1,a[i].l - 1,a[i].r)+1);
		modify(1,a[i].r,f[a[i].r]);
	}
	
	if(f[m] == INF)
	puts("-1");
	else
	printf("%lld\n",f[m]);
}

五、+扫描线 

247. 亚特兰蒂斯 - AcWing题库 

这道题运用了积分的思想，即将区间切分成非常多的长条，依据区间宽度有没有变化来判断，如下图：

 将区间划分后，要想求全部的面积并，就等于求每个区间面积和，那么怎么求出每个区间的和呢？

首先我们处理一下这个图，对于所有的矩形，将它左边的线段标记为1，右边的线段标记为-1，如上图，然后从左往右做，如果遇到1，就会将它的纵坐标上的记录数值累加1，遇到-1，则-1。这就相当于把遇到的每个区间看成是一个操作。

然后处理每个线的时候，看一下当前线的累计值是多少，就是被几个矩形的宽覆盖。

覆盖长度 * 横坐标差值 = 区间面积

所以整个问题需要支持两个操作：

1.将某个区间[L,R] + k  (k取0，1，-1）

2.求区间中长度大于0的区间总长，即矩形覆盖的范围

然后就可以用线段树来维护之前所说的纵坐标上记录的值，还需要维护一个当前区间被重复覆盖的次数，通过扫描线带有的性质优化，可以不需要懒标记

优化1：永远只考虑根节点的信息，这句话的意思是永远查询的是整个区间的信息，不会细分到子区间，query在第一次就会返回，不会递归

优化2：modify时也不需要pushdown，因为所有操作都是成对出现的，cnt 只有大于0和等于0的情况，如果大于0，不管是1，2，3……都只会被计算一次，所以不pushdown也没关系,如果等于0，那相当于没有懒标记，同样不需要pushdown

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm> 
#include<vector>
using namespace std;
const int N=100010;
int n;
struct segment//存储每个线段 
{
	double x,y1,y2;
	int k;//权值是k 
	bool operator< (const segment &t)const 
	{
		return x<t.x;
	}
}seg[N*2];
struct node
{
	int l,r;
	int cnt;
	double len;
}tr[N*8];
vector<double> ys;//离散化数组
int find(double y)
{
	return lower_bound(ys.begin(),ys.end(),y)-ys.begin();
} 
void pushup(int u)
{
	if(tr[u].cnt)
	tr[u].len=ys[tr[u].r+1]-ys[tr[u].l];
	else if(tr[u].l!=tr[u].r)
	{
		tr[u].len=tr[u<<1].len+tr[u<<1|1].len;
	}
	else
	tr[u].len=0;
}
void build(int u,int l,int r)
{
	tr[u]={l,r,0,0};
	if(l!=r)
	{
		int mid=l+r>>1;
		build(u<<1,l,mid),build(u<<1|1,mid+1,r);
	}
}
void modify(int u,int l,int r,int k)
{
	if(tr[u].l>=l&&tr[u].r<=r)
	{
		tr[u].cnt+=k;
		pushup(u);
	}
	else
	{
		int mid=tr[u].l+tr[u].r>>1;
		if(l<=mid)
		modify(u<<1,l,r,k);
		if(r>mid)
		modify(u<<1|1,l,r,k);
		pushup(u);
	}
}
int main()
{
	int t=1;
	while(scanf("%d",&n),n)
	{
		ys.clear();
		for(int i=0,j=0;i<n;i++)
		{
			double x1,y1,x2,y2;
			scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
			seg[j++]={x1,y1,y2,1};
			seg[j++]={x2,y1,y2,-1};
			ys.push_back(y1),ys.push_back(y2);
		}
		sort(ys.begin(),ys.end());
		ys.erase(unique(ys.begin(),ys.end()),ys.end());
		build(1,0,ys.size()-2);//存的是区间 
		sort(seg,seg+n*2);
		double res=0;
		for(int i=0;i<n*2;i++)
		{
			if(i>0)
			res+=tr[1].len*(seg[i].x-seg[i-1].x);
			modify(1,find(seg[i].y1),find(seg[i].y2)-1,seg[i].k);
		}
		printf("Test case #%d\n",t++);
		printf("Total explored area: %.2lf\n\n",res);
	}
}

除了这些，线段树还有很多应用，比如二维线段树，可以对矩形区间内的性质进行维护，通常实现方法为线段树套线段树，而线段树还可以和平衡树等等结合使用，网上有很多博客进行了介绍

相关文章：

  • 【学姐面试宝典】前端基础篇Ⅳ（JavaScript）
  • 本地JAR文件作为Gradle依赖项
  • Linux软件安装的4种方式
  • 自然语言处理Transformer模型最详细讲解（图解版）
  • JVM的组成
  • 【Rust日报】2022-10-15 Frui: 一个rust写的开发者友好的UI框架
  • Text Preprocessing - 文本预处理(RNN循环神经网络)
  • 【JavaScript设计模式】观察者模式
  • 【漏洞复现-splunk-信息泄露】vulfocus/splunk-cve_2018_11409
  • 赶紧进来看看---详解C/C++中的自定义类型:枚举和联合体
  • 神经网络的梯度实现
  • 网络版本计算器(再谈“协议“)
  • C++——string的简单使用与深浅拷贝的理解（建议收藏）
  • BGP综合实验
  • Day4——两两交换链表节点、删除链表第n个绩点、链表相交、环形链表||
  • ----------
  • 【407天】跃迁之路——程序员高效学习方法论探索系列（实验阶段164-2018.03.19）...
  • 【干货分享】SpringCloud微服务架构分布式组件如何共享session对象
  • Android Volley源码解析
  • Consul Config 使用Git做版本控制的实现
  • exif信息对照
  • Gradle 5.0 正式版发布
  • JavaScript创建对象的四种方式
  • Koa2 之文件上传下载
  • macOS 中 shell 创建文件夹及文件并 VS Code 打开
  • Sublime Text 2/3 绑定Eclipse快捷键
  • vue总结
  • 飞驰在Mesos的涡轮引擎上
  • 海量大数据大屏分析展示一步到位：DataWorks数据服务+MaxCompute Lightning对接DataV最佳实践...
  • 聊聊redis的数据结构的应用
  • 区块链共识机制优缺点对比都是什么
  • 我从编程教室毕业
  • 消息队列系列二（IOT中消息队列的应用）
  • 正则表达式
  • LevelDB 入门 —— 全面了解 LevelDB 的功能特性
  • shell使用lftp连接ftp和sftp,并可以指定私钥
  • #android不同版本废弃api，新api。
  • #vue3 实现前端下载excel文件模板功能
  • $HTTP_POST_VARS['']和$_POST['']的区别
  • (09)Hive——CTE 公共表达式
  • （1）(1.13) SiK无线电高级配置（五）
  • (13)Hive调优——动态分区导致的小文件问题
  • （超详细）2-YOLOV5改进-添加SimAM注意力机制
  • （二）c52学习之旅-简单了解单片机
  • （分布式缓存）Redis哨兵
  • （附源码）spring boot北京冬奥会志愿者报名系统 毕业设计 150947
  • (附源码)计算机毕业设计高校学生选课系统
  • （一）UDP基本编程步骤
  • (转)Windows2003安全设置/维护
  • . Flume面试题
  • .bat批处理（一）：@echo off
  • .mysql secret在哪_MYSQL基本操作（上）
  • .NET CORE 3.1 集成JWT鉴权和授权2
  • .NET Remoting Basic(10)-创建不同宿主的客户端与服务器端
  • .NET命名规范和开发约定