线段树详解
https://blog.csdn.net/sjystone/article/details/115398593

https://www.acwing.com/problem/content/246/

1.单点修改
2.查询区间内连续最大子段和

struct Node{
    int l ,r;
    int tmax    //最大连续子段和
    //父区间信息不可由左右子区间直接得到，需补充信息
    //需存储每个区间的最大连续后缀和和最大连续前缀和
    //父区间中横跨左右子区间的最大连续子段和 = 左子区间最大后缀和+右子区间最大前缀和
    int lmax    //最大前缀和
    int rmax    //最大后缀和
    int sum     //区间和，可以由子区间信息直接得到，故不用再定义其他信息
}

tmax = max(left_son.tmax, right_son.tmax, left_son.rmax + right_son.lmax)

对于lmax 
    -> left_son.lmax 或 left_son.sum + right_lmax
对于rmax
    -> right_son.rmax 或 right_son.sum + left_son.rmax

对于sum
    -> 父区间的sum可以直接由子区间sum算出

在查询操作时，若遇到横跨子区间的情况，需要合并

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

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

void pushup(Node &u, Node &l, Node &r)                  //由子区间更新父区间
{
    u.sum = l.sum + r.sum;                              //区间总和
    u.lmax = max(l.lmax, l.sum + r.lmax);               //前缀和 max(左子区间前缀和，左子区间总和+右子区间前缀和)
    u.rmax = max(r.rmax, r.sum + l.rmax);               //后缀和 max(右子区间后缀和，右子区间总和+左子区间后缀和)
    u.tmax = max(max(l.tmax, r.tmax), l.rmax + r.lmax); //区间最大值 max(左子区间前缀和，右子区间后缀和，(左子区间后缀和+右子区间前缀和))
}

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

void build(int u, int l, int r)                         //建树
{
    tr[u].l = l, tr[u].r = r;                           
    if ( l == r )
        tr[u].lmax = w[l], tr[u].rmax = w[l], tr[u].sum = w[l], tr[u].tmax = w[l];
    else
    {
        int mid = l + r >> 1;
        build(u << 1, l, mid);                          //递归建左树
        build(u << 1 | 1, mid + 1, r);                  //递归建右树
        pushup(u);                                      //更新信息
    }
}

void modify(int u, int x, int v)                        //修改
{
    if ( tr[u].l == x && tr[u].r == x ) 
        tr[u].lmax = v, tr[u].rmax = v, tr[u].tmax = v, tr[u].sum = v;
    else
    {
        int mid = tr[u].r + tr[u].l >> 1;
        if ( mid >= x ) modify(u << 1, x, v);           //往左递归(画图好理解)
        else modify(u << 1 | 1, x, v);                  //往右递归
        pushup(u);                                      //修改后更新信息
    }
}

Node query(int u, int l, int r)                         //查询，由于存在跨左右子区间的情况，返回结构体类型，再用pushup计算结果
{
    if ( tr[u].l >= l && tr[u].r <= r ) return tr[u];   //如果当前区间在查询区间内
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if ( mid >= r ) return query(u << 1, l, r);     
        else if ( mid < l ) return query(u << 1 | 1, l, r);
        else                                            //有跨子区间的情况，处理左右子区间，再用pushup求结果
        {
            Node left = query(u << 1, l ,r);
            Node right = query(u << 1 | 1, l, r);
            Node res;                                   //res看作left和right的父区间
            pushup(res, left, right);
            return res;
        }
    }
}

int main()
{
    cin >> n >> m;
    for ( int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
    build(1, 1, n);
    while ( m -- )
    {
        int k, x, y;
        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;
}