线段树最大子段

struct node{
  int l,r;
  int sum,ms;//maxsum
    int ml,mr;//maxl,maxr
}tree[N*4];
void PushUp(int i)
{
  tree[i].sum=tree[i<<1].sum+tree[i<<1|1].sum;
  tree[i].ml=max(tree[i<<1].sum+tree[i<<1|1].ml,tree[i<<1].ml);
  tree[i].mr=max(tree[i<<1|1].sum+tree[i<<1].mr,tree[i<<1|1].mr);
  tree[i].ms=max(max(tree[i<<1].ms,tree[i<<1|1].ms),tree[i<<1].mr+tree[i<<1|1].ml);
}
void build(int i,int l,int r)
{
  tree[i].l=l,tree[i].r=r;
  if(l==r)
  {
    tree[i].sum=tree[i].ml=tree[i].mr=tree[i].ms=a[l];
    return ;
  }
  int mid=(l+r)>>1;
  build(i<<1,l,mid);
  build(i<<1|1,mid+1,r);
  PushUp(i);
}
void update(int i,int pos,int val)
{
  if(tree[i].l==tree[i].r)
  {
    tree[i].ms=tree[i].ml=tree[i].mr=tree[i].sum=val;
    return ;
  }
  int mid=(tree[i].l+tree[i].r)>>1;
  if(pos<=mid)
    update(i<<1,pos,val);
  else update(i<<1|1,pos,val);
  PushUp(i);
}
node query(int i,int l,int r)
{
  if(l<=tree[i].l&&tree[i].r<=r)
    return tree[i];
  int mid=(tree[i].l+tree[i].r)>>1;
  if(r<=mid) return query(i<<1,l,r);
  else if(l>mid) return query(i<<1|1,l,r);
  else
  {
    node x=query(i<<1,l,r),y=query(i<<1|1,l,r),res;
    //合并答案 
    res.sum=x.sum+y.sum;
    res.ml=max(x.sum+y.ml,x.ml);
    res.mr=max(y.sum+x.mr,y.mr);
    res.ms=max(max(x.ms,y.ms),x.mr+y.ml);
    return res;
  }
}