对线段树Node中保存信息的学习

245. 你能回答这些问题吗
1.首先是单点修改，直接pushup
2.查询 区间内的最大子段和
一道题所有要维护的信息：
考虑当前信息，能否被算出来，如果不能，增加信息，再考虑增加的信息能否被算出来，直到完备性

struct Node
{
     int l, r;// 区间左右端点
     int tmax; // 最大连续子段和
     //横跨左右区间的最大子段和=左子_最大后缀+右子_最大前缀
     int lmax; //最大前缀和
     int rmax; //最大后缀和
     // tmax = max(left_son.tmax, right_son.tmax, left_son.rmax+right_son.lmax)
     // 新加的两个信息是否能得到
     //lmax情况1：left_son.lmax; 情况2：left_son.sum + right_son.lmax
     int sum; //新加：区间和,可以直接算出来
     //rmax同理
}

代码：

#include <bits/stdc++.h>

using namespace std;

const int N = 500010;

int n, m;
int w[N];
struct Node
{
    int l, r;
    int sum, lmax, rmax, tmax;
}tr[N * 4];

void pushup(Node &u, Node &l, Node &r)
{
    u.sum = l.sum + r.sum;
    u.lmax = max(l.lmax, l.sum + r.lmax);
    u.rmax = max(r.rmax, r.sum + l.rmax);
    u.tmax = max(l.tmax, max(r.tmax, l.rmax + r.lmax));    
}

void pushup(int u)
{
    pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}

void build(int u, int l, int r)
{
    if (l == r) tr[u] = {l, r, w[r], w[r], w[r], w[r]};
    else
    {
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

int modify(int u, int x, int v)
{
    if (tr[u].l == x && tr[u].r == x) tr[u] = {x, x, v, v, v, v};
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if (x <= mid) modify(u << 1, x, v);
        else modify(u << 1 | 1, x, v);
        pushup(u);
    }
}

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;
        }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
    build(1, 1, n);

    int k, x, y;
    while (m -- )
    {
        scanf("%d%d%d", &k, &x, &y);
        if (k == 1)
        {
            if (x > y) swap(x, y);
            printf("%d\n", query(1, x, y).tmax);
        }
        else modify(1, x, y);
    }

    return 0;
}