论线段树的调试

前言

线段树，一种很犇的数据结构，基本所有符合结合律的区间问题都可以使用线段树，但是，线段树对于新手来说并不好调，会直接造成RE,TLE等众多错误，本文将不再介绍线段树的基本思想，请新手大致了解后阅读本文
例题在洛谷 P3372 【模板】线段树 1

写出线段树

线段树最难的就是函数的嵌套，十分复杂，这里分别给出

一级函数

就是直接写出不需要嵌套的

ls–左儿子

根据一维数组存二叉树的特性，我们把当前下标乘$2$就行
（用inline和位运算会更快）
代码

inline int ls(int x){
	return x<<1;
}

rs–右儿子

同理可得，为左儿子$+1$
（乘$2$后必定为偶数，或$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$
代码

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$，不然访问到的就是错的！
2更新一个节点，必然会更新他的所有祖先节点，不然祖先节点的值是错的！
3分区间问题，包含返回，相交递推，相离舍去
4tag不管当前节点，只管儿子节点

常见的错误

1build时，一定注意a[k] = s[l]，而不是s[k]，不然会访问到$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！