AcWing245 线段树-单点修改+区间求最大连续子段和

题意

给定长度为 N 的数列 A，以及 M 条指令，每条指令可能是以下两种之一：
1. 1 x y,查询区间$[x,y]$种的最大连续子段和，即
$$
\max {x \leq l \leq r \leq y}\lbrace \sum{i=l}^{r} A[i] \rbrace
$$

2 x y,把$A[x]$改成$y$

对于每一个查询指令，输出一个整数表示答案。
题目来源于AcWing245，245. 你能回答这些问题吗 - AcWing题库

思路

以前我的线段树都是封装的，但是对于这样的询问需要返回不止一个值，例如这里在查询操作需要返回的是当前node结点，所以我之类还是不封装，写一个struct node类。

struct node
{
    int l,r,tmax,lmax,rmax,sum;
}tr[N<<2];

tmax表示的是当前结点的最大子段和。
lmax表示的是当前节点从左端点往右的最大子段和
rmax表示的是当前节点从右端点往左的最大子段和
sum表示的是当前节点的所有值的和

为什么需要设置lmax和rmax以及sum，因为我们在合并区间的时候，可能最大子段和在跨区间的部分，具体见pushup，好吧这就写哈哈！

这里为了简便写两个pushup，主要看另外一个，这个跟平时不一样，因为我这里传入的比较多，又是用的是node类，所以我这里传入的根节点，左右儿子结点，并且pushup里面是引用，可以修改。

对于维护四个值：
1. 维护sum，那当然是左右两个sum相加

维护lmax，那自然是左儿子的lmax与横跨两个结点的最大子段和来看，也就是左儿子的整段sum加上右儿子的lmax，这样就维护了当前根节点区间的`lmax

维护rmax，与上述一样，用右儿子的rmax与跨区间的比较，也就是右儿子的sum加上左儿子的rmax
维护当前结点的最大子段和tmax，有三种情况：左儿子的最大子段和tmax，右儿子的最大子段和tmax，横跨左右儿子的最大子段和左儿子的rmax和右儿子的lmax

inline void pushup(node &o,node &lc,node &rc)
{
    o.sum = lc.sum + rc.sum;
    o.lmax = Max(lc.lmax,lc.sum+rc.lmax);
    o.rmax = Max(rc.rmax,rc.sum+lc.rmax);
    o.tmax = Max( Max(lc.tmax,rc.tmax) , lc.rmax+rc.lmax );
}
inline void pushup(int o)
{
    pushup(tr[o],tr[lson],tr[rson]);
}

建树的话还是一样，一开始叶子结点的tmax,lmax,rmax,sum都等于a[l]。

inline void build(int o,int l,int r)
{
    tr[o].l = l; tr[o].r = r;
    if (l==r)
    {
        tr[o].tmax = tr[o].lmax = tr[o].rmax = tr[o].sum = a[l];
        return;
    }
    build(lson,l,mid);build(rson,mid+1,r);
    pushup(o);
}

然后来看修改，如果到叶子结点，那么需要将上述四个值都改为k，单点修改需要拿x去与mid比较。最后pushup更新。

inline void modify(int o,int x,int k)
{
    if (tr[o].l == tr[o].r) {tr[o] = {x,x,k,k,k,k};return;}
    if (x<=mid) modify(lson,x,k);
    else modify(rson,x,k);
    pushup(o);//递归更新
}

最后是查询，因为这里传入的变量比较多，所以就不再像以前那样写int query(...)了，而是返回一个node结点。
这里有两种写法，可以像y总那样分为三种情况，在左边，在右边，都在。也可以像我这样首先设置并且初始化两个结点，然后进行合并。
如果整段都在查询区间里面，那么就不需要往下了，直接return 当前结点。

inline node query(int o,int l,int r)
{
    if (l<=tr[o].l && tr[o].r<=r) return tr[o];
    node left={0,0,-inf,-inf,-inf,-inf},right={0,0,-inf,-inf,-inf,-inf},res;
    if (l<=mid) left = query(lson,l,r);
    if (r>mid) right = query(rson,l,r);
    pushup(res,left,right);
    return res;
}

也可以像y总那样

Node query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r) return tr[u];
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if (r <= mid) return query(u << 1, l, r);
        else if (l > mid) return query(u << 1 | 1, l, r);
        else
        {
            auto left = query(u << 1, l, r);
            auto right = query(u << 1 | 1, l, r);
            Node res;
            pushup(res, left, right);
            return res;
        }
    }
}

作者：yxc

所以线段树大致这样就完成了，单点修改也掌握了许多。

代码

const int N = 5e5+7;
int a[N];
#define lson (o<<1)
#define rson (o<<1|1)
#define mid ((tr[o].l+tr[o].r)>>1)
struct node
{
    int l,r,tmax,lmax,rmax,sum;
}tr[N<<2];
inline void pushup(node &o,node &lc,node &rc)
{
    o.sum = lc.sum + rc.sum;
    o.lmax = Max(lc.lmax,lc.sum+rc.lmax);
    o.rmax = Max(rc.rmax,rc.sum+lc.rmax);
    o.tmax = Max( Max(lc.tmax,rc.tmax) , lc.rmax+rc.lmax );
}
inline void pushup(int o)
{
    pushup(tr[o],tr[lson],tr[rson]);
}
inline void build(int o,int l,int r)
{
    tr[o].l = l; tr[o].r = r;
    if (l==r)
    {
        tr[o].tmax = tr[o].lmax = tr[o].rmax = tr[o].sum = a[l];
        return;
    }
    build(lson,l,mid);build(rson,mid+1,r);
    pushup(o);
}
inline void modify(int o,int x,int k)
{
    if (tr[o].l == tr[o].r) {tr[o] = {x,x,k,k,k,k};return;}
    if (x<=mid) modify(lson,x,k);
    else modify(rson,x,k);
    pushup(o);
}
inline node query(int o,int l,int r)
{
    if (l<=tr[o].l && tr[o].r<=r) return tr[o];
    node left={0,0,-inf,-inf,-inf,-inf},right={0,0,-inf,-inf,-inf,-inf},res;
    if (l<=mid) left = query(lson,l,r);
    if (r>mid) right = query(rson,l,r);
    pushup(res,left,right);
    return res;
}
#undef lson
#undef rson
#undef mid
int n,m,k,x,y;
inline void Case_Test()
{
    cin>>n>>m;
    for (int i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    while(m--)
    {
        cin>>k>>x>>y;
        if (k==1)
        {
            if (x>y) swap(x,y);
            cout<<query(1,x,y).tmax<<endl;
        }
        else 
            modify(1,x,y);
    }
}