论线段树的调试
论线段树的调试
前言
线段树，一种很犇的数据结构，基本所有符合结合律的区间问题都可以使用线段树，但是，线段树对于新手来说并不好调，会直接造成RE,TLE等众多错误，本文将不再介绍线段树的基本思想，请新手大致了解后阅读本文
例题在洛谷 P3372 【模板】线段树 1
写出线段树
线段树最难的就是函数的嵌套，十分复杂，这里分别给出
一级函数
就是直接写出不需要嵌套的
ls–左儿子
根据一维数组存二叉树的特性，我们把当前下标乘
2
2
2就行
（用inline和位运算会更快）
代码
inline int ls(int x){
return x<<1;
}
rs–右儿子
同理可得，为左儿子
+
1
+1
+1
（乘
2
2
2后必定为偶数，或
1
1
1会更快）
代码
inline int rs(int x){
return x<<1|1;
}
图示（包括ls和rs）
update–懒标记的生效
当前区间长度，乘以父节点的懒标记，加上去就可以
主要用于使懒标记转化为值
因为不遍历到下面，还要给自己打上懒标记
代码
void update(int k,int l,int r,int ftag){
a[k]+=(r-l+1)*ftag;
tag[k]+=ftag;
}
二级函数
嵌套了ls，rs，update
push_up–向上传值
我们更新儿子节点，一定要回归父节点
直接让父节点等于儿子节点
代码
void push_up(int k){
a[k] = a[ls(k)]+a[rs(k)];
}
push_down–向下传值
我们要更新或访问子节点了，懒标记不可能还在父节点上
我们把懒标记传下去，当前懒标记归零即可
代码
void push_down(int k,int l,int r){
int mid = (l+r)>>1;
update(ls(k),l,mid,tag[k]);
update(rs(k),mid+1,r,tag[k]);
tag[k] = 0;
}
三级函数
到了这里，函数加入了递归，开始作用于整棵线段树
build–树的建立
我们要先递归一遍，目的是把初始值传进去
到了最底层，肯定是直接等于输入数据了
向上回归时，就可以使用push_up
这样的话，树上的父节点等于子节点的和，懒标记就为
0
0
0
代码
void build(int k,int l,int r){
tag[k] = 0;
if(l==r){
a[k] = s[l];
return;
}
int mid = (l+r)>>1;
build(ls(k),l,mid);
build(rs(k),mid+1,r);
push_up(k);
}
add–区间加操作
就是题中给出的区间加和
我们设想一下，区间操作在线段树上，其实就是划分区间的过程
这就分情况了，请看图
注意，继续递推要清空当前懒标记，回归要用子节点改父节点
具体实现就不难了
代码（有注释）
void add(int ll,int rr,int l,int r,int k,int v){
if(ll<=l&&rr>=r){//更新区间
tag[k]+=v;
a[k]+=(r-l+1)*v;
return;
}
int mid = (l+r)>>1;
push_down(k,l,r);//清空懒标记
if(mid>=ll)add(ll,rr,l,mid,ls(k),v);//递推
if(mid+1<=rr)add(ll,rr,mid+1,r,rs(k),v);//if不成立，则和目标区间相离
push_up(k);//别忘了修改这个区间本身
}
query–区间访问
跟add都没区别
本质上还是分区间问题，参照上面的图
这次要有返回值，懒标记一定还是要更新的
代码
int query(int ll,int rr,int l,int r,int k){
if(ll<=l&&rr>=r){
return a[k];
}
int mid = (l+r)>>1,ans = 0;
push_down(k,l,r);
if(mid>=ll)ans+=query(ll,rr,l,mid,ls(k));
if(mid+1<=rr)ans+=query(ll,rr,mid+1,r,rs(k));
push_up(k);
return ans;
}
调试线段树
线段树的规律
1访问一个节点，则它的所有祖先节点的懒标记必定为
0
0
0，不然访问到的就是错的！
2更新一个节点，必然会更新他的所有祖先节点，不然祖先节点的值是错的！
3分区间问题，包含返回，相交递推，相离舍去
4tag不管当前节点，只管儿子节点
常见的错误
1build时，一定注意a[k] = s[l]，而不是s[k]，不然会访问到
0
0
0
2一定注意，除了push_up和清零tag，其他都是+=，不然会WA
AC代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 114514;
int n,m,a[N<<2],s[N],tag[N<<2];
inline int ls(int x){
return x<<1;
}
inline int rs(int x){
return x<<1|1;
}
void update(int k,int l,int r,int ftag){
a[k]+=(r-l+1)*ftag;
tag[k]+=ftag;
}
void push_up(int k){
a[k] = a[ls(k)]+a[rs(k)];
}
void push_down(int k,int l,int r){
int mid = (l+r)>>1;
update(ls(k),l,mid,tag[k]);
update(rs(k),mid+1,r,tag[k]);
tag[k] = 0;
}
void build(int k,int l,int r){
tag[k] = 0;
if(l==r){
a[k] = s[l];
return;
}
int mid = (l+r)>>1;
build(ls(k),l,mid);
build(rs(k),mid+1,r);
push_up(k);
}
void add(int ll,int rr,int l,int r,int k,int v){
if(ll<=l&&rr>=r){
tag[k]+=v;
a[k]+=(r-l+1)*v;
return;
}
int mid = (l+r)>>1;
push_down(k,l,r);
if(mid>=ll)add(ll,rr,l,mid,ls(k),v);
if(mid+1<=rr)add(ll,rr,mid+1,r,rs(k),v);
push_up(k);
}
int query(int ll,int rr,int l,int r,int k){
if(ll<=l&&rr>=r){
return a[k];
}
int mid = (l+r)>>1,ans = 0;
push_down(k,l,r);
if(mid>=ll)ans+=query(ll,rr,l,mid,ls(k));
if(mid+1<=rr)ans+=query(ll,rr,mid+1,r,rs(k));
push_up(k);
return ans;
}
signed main(){
cin>>n>>m;
for(int i = 1;i<=n;i++){
cin>>s[i];
}
build(1,1,n);
for(int i = 1;i<=m;i++){
int q;
cin>>q;
if(q==1){
int x,y,k;
cin>>x>>y>>k;
add(x,y,1,n,1,k);
}else if(q==2){
int x,y;
cin>>x>>y;
cout<<query(x,y,1,n,1)<<endl;
}
}
return 0;
}
后记
线段树其实是由函数组成的，但是单看每一个函数，都不难
那为什么不会呢，因为函数之间的关系，一般老师是不会讲的
对于初学者好像也不能这么讲
为什么写不出来，调不明白，就是因为没用真正理解
我们在考虑问题时也是有顺序的，顺序选对了，才能有最小的时间复杂度
所有人都觉得二分，前缀和简单
我们把更复杂的算法分成简单的部分，才能更好的理解
本文作者是蒟蒻，如有错误请各位神犇指点！
森林古猿出品，必属精品，请认准CSDN森林古猿1！
原文地址：https://blog.csdn.net/senlinguyvan1/article/details/143088251
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！