线段树
基础线段树
一，原理
选自AC wing 算法提高课（侵删！）
2，建树操作
目的：把一个区间转换成一个可维护的树结构
struct segmenttree{
int l,r,v;
int sum,add;
（还可以添加好多好多需要的数据）
#define sum(x) tr[x].sum
#define add(x) tr[x].add
#define l(x) tr[x].l
#define r(x) tr[x].r
}tr[M*4];
void build(int p,int l,int r)
{
tr[p]={l,r};
if(l==r)return ;（这里你可以初始化一些东西）
int mid= l+r >> 1;
//区间分割操作
build (p<<1,l,mid);
build (p<<1|1,mid+1,r);
}
2，pushup（由子节点更新父节点）
11，区间最值
void pushup(int i){
tr[i].v=max(tr[i<<1].v,tr[i<<1|1].v);}
22，区间最大子段和
3，pushdown__spread（由父节点更新子节点）
要素：延时标记（满足信息可减性）
- 概念：如果我们需要修改一个区间，我们不需要一个一个更改。对于被修改区间完全覆盖的节点，我们可一直更新它们的值而不去更新它们下面的子节点的值。
- 取而代之的是，在这个节点打上一个懒标记，代表它的子节点还没更新。当我们需要再次修改或者查询时，要是碰到带着懒标记的节点，再去更新。
- 性质：具有懒标记的节点，他的信息应当已经被更新过，而他子节点的信息还没有被更新。
- 以上概念，性质转自：xxx 的线段树blog
分类：add（增量延时标记）
行为：
1，延迟标记下传作用子级节点
2，子级延迟标记激活，继承父级的标记，进行叠加
3，父级延迟标记注销
void pushdown(int x)
{
sum(x<<1)+=add(x)*(r(x<<1)-l(x<<1)+1);
sum(x<<1|1)+=add(x)*(r(x<<1|1)-l(x<<1|1)+1);
add(x<<1|1)+=add(x);
add(x<<1)+=add(x);
add(x)=0;
}
4，区间修改操作
请注意pushup和pushdown的位置
- 在需要递归子区间节点时，延迟标记一定要下传（pushdown）
- 在回溯父级节点的时候，一定要更新一下父节点的数据（pushup）
void change (int p,int l,int r,int d,int x)
{
int ll=l(p); int rr=r(p);
if(l<=ll&&r>=rr){
sum(p)+=(long long )d*(r(p)-l(p)+1);
add(p)+=d;
return ; }
pushdown(p);
int mid=ll+rr >>1;
if(l<=mid)change (p<<1,l,r,d);
if(r>mid)change (p<<1|1,l,r,d);
pushup(p);
}
5，单点修改操作
void change (int p,int x,int v)(节点编号，target节点，修改数据)
{
if(tr[p].l==tr[p].r&&tr[p].l==x)
{
tr[p].v=v;return ;
}
int mid=tr[p].l+tr[p].r >> 1;
if(x <= mid)change (p*2,x,v);
else change (p*2+1,x,v);
pushup(p);
}
6，区间查询操作
long long ask(int p,int l,int r)
{
int ll=l(p); int rr=r(p);
if(l<=ll&&r>=rr)return sum(p);
pushdown(p);
int mid= ll+rr >>1;
long long val=0;
if(l<=mid)val+=ask (p<<1,l,r);
if(r>mid)val+=ask (p<<1|1,l,r);
return val;
}