算法竞赛进阶指南，215页， 线段树
本题要点：
1、线段树的每个节点维护的信息
线段的左右端点：L 和 R
dat : 区间最大连续子段和
sum : 区间所有数的总和
lmax: 紧靠左端的最大连续子段的总和
rmax: 紧靠右端的最大连续子段的总和
2、线段树 的父节点 p 和左孩子 2 * p, 右孩子 2 * p + 1 的信息关系, 在build 和 change函数中维护好节点的信息
t[p].sum = t[2 * p].sum + t[2 * p + 1].sum;
t[p].lmax = max(t[2 * p].lmax, t[2 * p].sum + t[2 * p + 1].lmax);
t[p].rmax = max(t[2 * p + 1].rmax, t[2 * p + 1].sum + t[2 * p].rmax);
t[p].dat = max(t[p * 2].dat, t[2 * p + 1].dat);
t[p].dat = max(t[p].dat, t[2 * p].rmax + t[2 * p + 1].lmax);
3、查询每一段 [L, R] 的 区间最大连续子段和 时，分类讨论：
区间[L, R] 仅仅与左孩子有交集
区间[L, R] 仅仅与右孩子有交集，
区间[L, R] 同时与左右孩子有交集，形式类似于上面公式；
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MaxN = 500010;
int a[MaxN];
int n, m;struct segTree
{
int L, R;int dat; //区间最大连续子段和int sum; //区间总和int lmax, rmax;
}t[MaxN * 4];void build(int p, int L, int R)
{
t[p].L = L, t[p].R = R;if(L == R) //叶子节点{
t[p].sum = t[p].lmax = t[p].rmax = t[p].dat = a[L];return;}int mid = (L + R) / 2;build(p * 2, L, mid); //左子节点build(p * 2 + 1, mid + 1, R); //右子节点t[p].sum = t[2 * p].sum + t[2 * p + 1].sum;t[p].lmax = max(t[2 * p].lmax, t[2 * p].sum + t[2 * p + 1].lmax);t[p].rmax = max(t[2 * p + 1].rmax, t[2 * p + 1].sum + t[2 * p].rmax);t[p].dat = max(t[p * 2].dat, t[2 * p + 1].dat);t[p].dat = max(t[p].dat, t[2 * p].rmax + t[2 * p + 1].lmax);
}void change(int p, int x, int v)
{
if(t[p].L == t[p].R){
t[p].sum = t[p].lmax = t[p].rmax = t[p].dat = v;return;}int mid = (t[p].L + t[p].R) / 2;if(x <= mid){
change(p * 2, x, v);}else{
change(p * 2 + 1, x, v);}t[p].sum = t[2 * p].sum + t[2 * p + 1].sum;t[p].lmax = max(t[2 * p].lmax, t[2 * p].sum + t[2 * p + 1].lmax);t[p].rmax = max(t[2 * p + 1].rmax, t[2 * p + 1].sum + t[2 * p].rmax);t[p].dat = max(t[p * 2].dat, t[2 * p + 1].dat);t[p].dat = max(t[p].dat, t[2 * p].rmax + t[2 * p + 1].lmax);
}segTree ask(int p, int L, int R)
{
if(L <= t[p].L && R >= t[p].R){
return t[p];}segTree ans, left, right;ans.dat = ans.lmax = ans.rmax = -0x3f3f3f3f; //负无穷ans.sum = 0;int mid = (t[p].L + t[p].R) / 2;if(L <= mid){
left = ask(p * 2, L, R);// 左孩子有重叠 ans.sum += left.sum;ans.dat = max(ans.dat, left.dat);ans.lmax = left.lmax;}if(R > mid){
right = ask(p * 2 + 1, L, R);//右孩子有重叠ans.sum += right.sum;ans.dat = max(ans.dat, right.dat);ans.rmax = right.rmax;}if(L <= mid && R > mid) //左右孩子均有重叠{
ans.lmax = max(left.sum + right.lmax, ans.lmax);ans.rmax = max(right.sum + left.rmax, ans.rmax);ans.dat = max(ans.dat, left.rmax + right.lmax);}return ans;
}int main()
{
scanf("%d%d", &n, &m);for(int i = 1; i <= n; ++i){
scanf("%d", &a[i]);}build(1, 1, n);int cmd, x, y;for(int i = 0; i < m; ++i){
scanf("%d%d%d", &cmd, &x, &y);if(1 == cmd){
if(x > y){
swap(x, y);}printf("%d\n", ask(1, x, y).dat); }else{
change(1, x, y); }}return 0;
}/* 5 3 1 2 -3 4 5 1 2 3 2 2 -1 1 3 2 *//* 2 -1 */