线段树相关
2026-07-12 21:40:00
发布于：浙江
1阅读
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作为目前所在的区间。
线段树-懒标记的使用
例题：线段树二
线段树二相比一多了乘法。
所以需要两个懒标记数组（一个记录加法，一个记录乘法）
另外还需要注意的是：
线段树二的树懒标记和线段树一的树懒标记不一样。
不仅仅只是单纯地加了一个乘法。
还有顺序的区别。
线段树二需要：先乘再加。
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.线段树的两个模板都是一种点线段树，而不是一种区间线段树。
区间线段树相比点线段树要考虑更多。
比如：是左闭右开还是左闭右闭。
建议写左闭右闭。
这里空空如也
有帮助，赞一个