Magic-Segment Tree
MagicStorm · · 算法·理论
Segment Tree-线段树
前言：线段树为OI生涯中超级重要的一个板块，应用范围快，易思考的数据结构，所以一定要完全掌握。
- 在解决区间问题时，参考区间 DP，我们可以将2个小区间合并成一个大区间，那我们将两个小区间分别作为合成的大区间的左子节点和右子节点，就可以得到一棵二叉树。前言也提到过，适合解决大部分区间问题。每个区间代表的意义，也可称为维护的东西。
Build-建树
某些情况要对区间（包括单个的叶子节点）进行初始化时，就一般要建一棵树。
考虑如何建树，我们可以用
如以
void build(int l,int r,int root){
if(l==r){
tree[root]x=1;
return ;
}
auto lp=(root<<1),rp=(lp+1),mid=(l+r)/2;
build(l,mid,lp),build(mid+1,r,rp);
tree[root]=calculation(tree[lp],tree[rp]);
}Lazy Tag-区间修改
单点修改有兴趣可以自己搜，但我不太建议，毕竟区间修改的左端点等于有端点就是单点了。
众所周知单点修改为 闲话:因为这个标记优化了区间修改，而且写起也简单，懒人专用)，然后我们每次将父节点的标记向子节点传递，并将子节点的值进行修改(push_down)。如当此时当前区间属于所需修改区间则直接修改当前节点的值，如果此时区间超过了所需修改区间则不修改。就做到了
void push_down(int l,int r,int root){
auto lp=(root<<1),rp=(lp|1),mid=(l+r)/2;
tree[lp].tag+=tree[root].tag,tree[rp].tag+=tree[root].tag;
tree[lp].x+=(mid-l+1)*tree[root].tag;
tree[rp].x+=(r-mid)*tree[root].tag;
// cerr<<"Fuck Colin:"<<tree[root].x<<" "<<tree[lp].x<<" "<<tree[rp].x<<endl;
tree[root].tag=0;
}
void modify(int lc,int rc,int l,int r,zjj x,int root){
if(l>rc||r<lc) return ;
if(l<=lc&&r>=rc){
tree[root].tag+=x;
tree[root].x+=x*(rc-lc+1);
return ;
}
auto lp=(root<<1),rp=lp+1,mid=(lc+rc)>>1;
push_down(lc,rc,root);
modify(lc,mid,l,r,x,lp),modify(mid+1,rc,l,r,x,rp);
tree[root]=calculation(tree[lp],tree[rp]);
}
qry-查询
跟