线段树小技巧
·线段树维护最大子段和
1.需要维护四个信息
开结构体一般更方便一些
struct seg{
int sum;//区间总和
int mxs;//最大子段和
int ls;//左起最大字段和
int rs;//右起最大字段和
}tr[N<<1];
2.pushup改为返回一个结构体,便于后面查询
pushup
seg pushup(seg l,seg r){
seg k;
k.sum=l.sum+r.sum;
k.mxs=max(max(l.mxs,r.mxs),l.rs+r.ls);
k.ls=max(l.ls,l.sum+r.ls);
k.rs=max(r.rs,r.sum+l.rs);
return k;
}
其他函数（建树、修改）
tr[u]=pushup(tr[lc],tr[rc]);
3.查询时也返回一个结构体
四种情况分类讨论
seg qry(int u,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr) return tr[u];
if(qr<=mid) return qry(lc,l,mid,ql,qr);//全部在左区间
if(ql>mid) return qry(rc,mid+1,r,ql,qr);//全部在右区间
return pushup(qry(lc,l,mid,ql,qr),qry(rc,mid+1,r,ql,qr));//合并左右答案
}
··线段树维护最值
查询某区间在全集中的补集的信息
这里以最小值为例
if(r<ql||l>qr)return mn[u];
if(ql<=l&&r<=qr)return 1e16;
···对于每个点维护区间和
待补