不重点介绍线段树概念了，就大概贴一下几部分的模板
build(); 建立线段树
update(); 更新操作(单点、区间更新)
query(); 查询操作(单点、区间查询)
pushup(); 向上回溯
pushdown(); 向下延时更新
先说明一下数组
int s[maxx],mx[maxx<<2]; //s为输入数组，mx为求和或最值数组
int lazy[maxx<<2]; //lazy为延迟标记首先，build线段树
void build(int l,int r,int rt) //rt为节点编号，l，r为节点区间
{if(l==r) //寻找到一个叶节点{mx[rt]=s[l];return ;}int mid=(l+r)>>1;build(l,mid,rt<<1); //左右递归build(mid+1,r,rt<<1|1); pushup(rt); //向上回溯
}pushup
void pushup(int rt) //向上回溯
{mx[rt]=max(mx[rt<<1],mx[rt<<1|1]);
}update分为单点更新和区间更新（需要延迟标记）
先来简单一些的单点更新
void update(int L,int s,int l,int r,int rt) //单点更新
{if(l==r) //找到叶节点，进行修改{mx[rt]=s;return ;}int mid=(l+r)>>1;if(L<=mid) update(L,s,l,mid,rt<<1); //判断调用左子树还是右子树else update(L,s,mid+1,r,rt<<1|1);pushup(rt); //向上回溯
}接下来的区间更新需要用到延迟标记，这里用lazy表示
当有[l，r]区间内的值都需要改变时，若是使用单点更新会极大浪费时间，增加复杂度，这里lazy就是为了降低时间复杂度而存在，是线段树比较快的精华所在
第一次学lazy怎么都理解不了，这次学习看了大牛的博客后，个人觉得线段树的lazy标记和差分数组很像
条件都是需要改变一个区间内的所有值，使用一个特定的数组，在特定位置进行标记，之后在需要展开计算的时候，再进行所有的计算
lazy标记的本节点已经更新，但是其子节点还需要更新，其余代码里详述
（差分数组就不仔细介绍了，毕竟线段树模板）
void Update(int L,int R,int c,int l,int r,int rt) //区间更新
{if(L<=l && R>=r){ //找到可更新区间mx[rt]+=c*(r-l+1); //本节点加上其所有子节点的值lazy[rt]+=c; //对本节点lazy进行标记return ;}int mid=(l+r)>>1; pushdown(rt,mid-l+1,r-mid); //向子节点延时更新if(L<=mid) Update(L,R,c,l,mid,rt<<1); //判断调用左子树还是右子树if(R>mid) Update(L,R,c,mid+1,r,rt<<1|1);pushup(rt);
}pushdown 向下延时更新
void pushdown(int rt,int l,int r) //向下延时更新
{if(lazy[rt]){ //因为可能已经有值，所以这里都是 +=lazy[rt<<1]+=lazy[rt]; //左子节点lazy标记更新lazy[rt<<1|1]+=lazy[rt]; //右子节点lazy标记更新mx[rt<<1]+=lazy[rt]*l; //左子节点进行更新mx[rt<<1|1]+=lazy[rt]*r; //右子节点进行更新lazy[rt]=0; //将该标记清零}
}最后还有query
单点查询
int query(int L,int l,int r,int rt) //单点查询
{if(l==r) return mx[rt]; //找到节点直接返回int mid=(l+r)>>1;int ret=0;if(L<=mid) ret=max(ret,query(L,l,mid,rt<<1)); //判断调用左子树还是右子树else ret=max(ret,query(L,mid+1,r,rt<<1|1));return ret;
}区间查询
int query(int L,int R,int l,int r,int rt) //区间查询
{if(L<=l && R>=r) return mx[rt]; //区间内直接返回int mid=(l+r)>>1;pushdown(rt,mid-l+1,r-mid); //向下更新，否则结果可能不正确int ret=0;if(L<=mid) ret=max(ret,query(L,R,l,mid,rt<<1)); //判断调用左子树右子树if(R>mid) ret=max(ret,query(L,R,mid+1,r,rt<<1|1));return ret;
}以上都是递归版的线段树
（非递归版的还没有学习）