论线段树的调试

前言

写出线段树

一级函数

ls--左儿子

rs--右儿子

update--懒标记的生效

二级函数

push_up--向上传值

push_down--向下传值

三级函数

build--树的建立

add--区间加操作

query--区间访问

调试线段树

线段树的规律

常见的错误

AC代码

后记

前言

线段树，一种很犇的数据结构，基本所有符合结合律的区间问题都可以使用线段树，但是，线段树对于新手来说并不好调，会直接造成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