描述
小新经常陪小白去公园玩，也就是所谓的遛狗啦…在小新家附近有一条“公园路”，路的一边从南到北依次排着n个公园，小白早就看花了眼，自己也不清楚该去哪些公园玩了。
一开始，小白就根据公园的风景给每个公园打了分-.-。小新为了省事，每次遛狗的时候都会事先规定一个范围，小白只可以选择第a个和第b个公园之间（包括a、b两个公园）选择连续的一些公园玩。小白当然希望选出的公园的分数总和尽量高咯。同时，由于一些公园的景观会有所改变，所以，小白的打分也可能会有一些变化。
那么，就请你来帮小白选择公园吧。
输入格式
第一行，两个整数N和M，分别表示表示公园的数量和操作（遛狗或者改变打分）总数。
接下来N行，每行一个整数，依次给出小白 开始时对公园的打分。
接下来M行，每行三个整数。第一个整数K，1或2。K=1表示，小新要带小白出去玩，接下来的两个整数a和b给出了选择公园的范围（1≤a,b≤N）；K=2表示，小白改变了对某个公园的打分，接下来的两个整数p和s，表示小白对第p个公园的打分变成了s（1≤p≤N）。
其中，1≤N≤500 000，1≤M≤100 000，所有打分都是绝对值不超过1000的整数。
输出格式
小白每出去玩一次，都对应输出一行，只包含一个整数，表示小白可以选出的公园得分和的最大值。
测试样例1
输入
5 3
1 2 -3 4 5
1 2 3
2 2 -1
1 2 3
输出
2
-1
每个节点维护一个left,right,mid,sum，分别表示 从左 / 从右 / 全部 开始的最大值 和 整个节点的和
这样可以类似DP写出转移方程
当前sum＝左儿子sum＋右儿子sum
当前left＝max｛左儿子left，左儿子sum＋右儿子left ｝
当前right＝max｛右儿子right，右儿子sum＋左儿子right｝
当前mid＝max｛左儿子mid，右儿子mid，左儿子right＋右儿子left ｝
这样每次更新出每个节点的各个值，ok
**数据里面当输入 1 a b 的时候有可能出现 a>b ！！！
所以一定要swap过来**
#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN=500000;
int n,m;
struct node
{int sum,lm,rm,tot;
}tree[4*MAXN+1];
inline void update(int num)
{tree[num].sum=tree[2*num].sum+tree[2*num+1].sum;tree[num].lm=max(tree[2*num].lm,tree[2*num].sum+tree[2*num+1].lm);tree[num].rm=max(tree[2*num+1].rm,tree[2*num+1].sum+tree[2*num].rm);tree[num].tot=max(tree[2*num].rm+tree[2*num+1].lm,max(tree[2*num].tot,tree[2*num+1].tot));
}
inline void chg(int l,int r,int num,int p,int s)
{if(l==r){tree[num].sum=tree[num].tot=tree[num].rm=tree[num].lm=s;return ;}int mid=l+r>>1;if(p<=mid)chg(l,mid,2*num,p,s);elsechg(mid+1,r,2*num+1,p,s);update(num);
}
inline node query(int l,int r,int num,int a,int b)
{if(a<=l&&b>=r)return tree[num];int mid=l+r>>1;if(b<=mid)return query(l,mid,2*num,a,b);else if(a>=mid+1)return query(mid+1,r,2*num+1,a,b);else{node tmp1,tmp2,res;tmp1=query(l,mid,2*num,a,b);tmp2=query(mid+1,r,2*num+1,a,b);res.sum=tmp1.sum+tmp2.sum;res.lm=max(tmp1.lm,tmp1.sum+tmp2.lm);res.rm=max(tmp2.rm,tmp2.sum+tmp1.rm);res.tot=max(max(tmp1.tot,tmp2.tot),tmp1.rm+tmp2.lm);return res;}
}
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){int x;scanf("%d",&x);chg(1,n,1,i,x);}for(int i=1;i<=m;i++){int a,b,k,p,s;scanf("%d",&k);if(k==1){scanf("%d%d",&a,&b);if(a>b)swap(a,b);printf("%d\n",query(1,n,1,a,b).tot);}else{scanf("%d%d",&p,&s);chg(1,n,1,p,s);}}return 0;
}