线段树相关 - “料峭春风吹酒醒，微冷"

ToTheSun

2026-07-14 07:58:40

发布于：浙江

13阅读

0回复

0点赞

注：本文不用于传给他人阅读学习，仅个人记录

模板

需要完成的：
1.将某区间每一个数加上k
2.求某区间每一个数的和

代码主要构成：

一.区间加

void qjj(int now,int L,int R,int l,int r,ll kk){
	//现在所在节点编号，要加上kk的区间的左右端点编号，目前所在的左右端点编号
	if(Whole_bh(L,R,l,r)){
		make_tag(now,kk,l,r);
		return;
	} 
	if(Outof_qj(L,R,l,r))return;
	int mid=(l+r)>>1;
	pushdown(l,r,now,mid);
	qjj(now*2,L,R,l,mid,kk),qjj(now*2+1,L,R,mid+1,r,kk);
	pushup(now);
}

挖空变成通用模板：

void qjj(当前节点编号，目标区间左右节点编号，现在所在区间左右节点编号){
	//现在所在节点编号，要加上kk的区间的左右端点编号，目前所在的左右端点编号
	if(目标区间包含现在所在区间){
		打上懒标记
	} 
	if(目标区间于现在所在区间完全不重叠)return;
	int mid=(l+r)>>1;
    下放当前节点所含有的懒标记，清空当前节点懒标记
	遍历左子节点，遍历右子节点
	将当前节点由左子节点和右子节点重构
}

二.求去区间和

ll qjh(int u,int L,int R,int l,int r){
	//求取区间和 
	//当前结点编号，要求取区间左右端点，目前遍历到的区间的左右端点
	if(Whole_bh(L,R,l,r))return w[u];
	if(Outof_qj(L,R,l,r))return 0;
	int mid=(l+r)>>1;
	pushdown(l,r,u,mid);
	return qjh(u*2,L,R,l,mid)+qjh(u*2+1,L,R,mid+1,r);
}

挖空：

ll qjh(当前节点编号，目标区间左右端点，目前遍历到的区间的左右端点){
	//求取区间和 
	区间加同理
	int mid=(l+r)>>1;
	下放标记
	返回左子节点和右子节点值
}

线段树相关要点（易错点）：
1.在函数中传入的L,R,l,r有很多。要将它们是代表目标区间还是目前遍历到的区间确定下来。
这里统一使用l,r作为目前所在的区间。(另外有可能在打代码的时候把L达成l)
2.空间最好开四倍
3.通常要离开long long 最好注意范围

线段树-懒标记的使用
例题：线段树二
线段树二相比一多了乘法。
所以需要两个懒标记数组（一个记录加法，一个记录乘法）

另外还需要注意的是：
线段树二的树懒标记和线段树一的树懒标记不一样。
不仅仅只是单纯地加了一个乘法。
还有顺序的区别。

线段树二需要：先乘再加。

void make_tag(int now,ll kkj,ll kkc,int l,int r){
	//现在所在节点编号，树懒加，树懒乘，左端点，右端点 
	w[now]=((w[now]*kkc)%mod+((r-l+1)*kkj)%mod)%mod;
	lzy2[now]=(kkc*lzy2[now])%mod;
	lzy[now]=(kkj+(lzy[now]*kkc)%mod)%mod;
}

线段树-扫描线（矩阵面积并）

扫描线是一种运用于二维平面上的技巧。

这道题就已经是线段树的一种变式了。

需要关注的点：
1.线段树的两个模板都是一种点线段树，而不是一种区间线段树。
区间线段树相比点线段树要考虑更多。
比如：是左闭右开还是左闭右闭。

建议写左闭右闭。

多做点别的

小白逛公园

先不写公园了，昨天新弄了一道模板变式题目。
https://xinyoudui.com/ac/contest/747011268000BED0905C9C/problem/8286
火车线路

#include<bits/stdc++.h>
using namespace std;
const int N=6e4+5;
int c,s,r;//c个城市，s个座位，r个预定 
int w[N*4],lzy[N*4];
void pushup(int x){
	w[x]=min(w[x*2],w[x*2+1]);
}
void build(int u,int l,int r,int val){
	if(l==r){
		w[u]=val;
		return;
	}
	int mid=(l+r)>>1;
	build(u*2,l,mid,val),build(u*2+1,mid+1,r,val);
	pushup(u);
}
void get_lzy(int u,int val){
	lzy[u]+=val;
	w[u]-=val;
	return;
}
void pushdown(int u){
	get_lzy(u*2,lzy[u]);
	get_lzy(u*2+1,lzy[u]);
	lzy[u]=0;
}
int cha(int u,int l,int r,int L,int R){
	if(L<=l&&r<=R)return w[u];
	if(r<L||R<l)return INT_MAX;
	int mid=(l+r)>>1;
	pushdown(u);
	return min(cha(u*2,l,mid,L,R),cha(u*2+1,mid+1,r,L,R));
}
void xdsj(int u,int l,int r,int L,int R,int val){
	if(L<=l&&r<=R){
		get_lzy(u,val);
		return;
	}
	if(r<L||R<l)return;
	int mid=(l+r)>>1;
	pushdown(u);
	xdsj(u*2,l,mid,L,R,val),xdsj(u*2+1,mid+1,r,L,R,val);
	pushup(u);
	return;
}
int main(){
	cin>>c>>s>>r;
	build(1,1,c,s);
	for(int i=1;i<=r;i++){
		int o,d,n;
		//起点站，终点站，需要的座位数量
		cin>>o>>d>>n;
		int a=cha(1,1,c,o,d-1); 
		if(a<n){
			cout<<"N\n";
			continue;
		}
		xdsj(1,1,c,o,d-1,n);
		cout<<"T\n";
	}
	return 0;
}