http://oi.nks.edu.cn/en/Problem/Details/1316
小新经常陪小白去公园玩，也就是所谓的遛狗啦…在小新家附近有一条“公园路”，
路的一边从南到北依次排着n个公园，小白早就看花了眼，自己也不清楚该去哪些公园玩了。
一开始，小白就根据公园的风景给每个公园打了分-.-。小新为了省事，
每次遛狗的时候都会事先规定一个范围，小白只可以选择第a个和第b个公园之间
（包括a、b两个公园）选择连续的一些公园玩。
小白当然希望选出的公园的分数总和尽量高咯。
同时，由于一些公园的景观会有所改变，
所以，小白的打分也可能会有一些变化。那么，就请你来帮小白选择公园吧。
这道题，其实是并不是非常难，只不过楼主卡了很久才过的:
首先我们先建树：然后再进行更新或者询问，更新是简单的点更新，
具体询问看下面
#include<cstdio>
#include<iostream>
using namespace std;
const int Max=2e6+5;
int l[Max],r[Max];//左端点和右端点
int lmax[Max],rmax[Max],maxx[Max];
//lmax指从最左边往右开始算的线段最大，rmax指从最有右边往左开始算的线段最大，
//而maxx指的是这一段中和最大的一段
int sum[Max];//只这一段所有景点值的和
int s[500005];
int s1;
int n,m;
int xx,yy;
int getl(int i){//算左边最大
return max(lmax[i],sum[i]+lmax[i+1]);
}
int getr(int i){//算右边最大
return max(rmax[i+1],sum[i+1]+rmax[i]);
}
int get(int i){//算综合最大
return max(max(maxx[i],maxx[i+1]),rmax[i]+lmax[i+1]);
}
void magic(int x,int y){
sum[y]=lmax[y]=rmax[y]=maxx[y]=x;
}
void buildtree(){
s1=1;
while(s1<n)s1*=2;
for(int i=s1*2-1;i>=s1;i--){
l[i]=r[i]=i-s1+1;
magic(s[i-s1+1],i);
}
for(int i=s1-1;i>=1;i--){
l[i]=l[i<<1],r[i]=r[(i<<1)+1];
sum[i]=sum[(i<<1)+1]+sum[i<<1];
lmax[i]=getl((i<<1));rmax[i]=getr((i<<1));
maxx[i]=get((i<<1));
}
}
void update(int x,int y){
magic(x,y);
while(y){
y/=2;
sum[y]=sum[(y<<1)+1]+sum[y<<1];
lmax[y]=getl((y<<1));rmax[y]=getr((y<<1));maxx[y]=get((y<<1));
}
}
int ask(int l,int r,int i);
int getleft(int l1,int r1,int i){
if(r1==r[i])return lmax[i];
int mid=(l[i]+r[i])/2;
if(mid>=r1)return getleft(l1,r1,i*2);
else return max(sum[2*i]+getleft(mid+1,r1,i*2+1),lmax[i*2]);
}
int getright(int l1,int r1,int i){
if(l1==l[i])return rmax[i];
int mid=(l[i]+r[i])/2;
if(l1>mid)return getright(l1,r1,i*2+1);
else return max(sum[2*i+1]+getright(l1,mid,i*2),rmax[i*2+1]);
}
int k,x,y;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&s[i]);
buildtree();
for(int i=1;i<=m;i++){
scanf("%d%d%d",&k,&x,&y);
if(k==2)update(y,x+s1-1);
else {
if(x>y)swap(x,y);
printf("%d ",ask(x,y,1));
}
}
return 0;
}
int ask(int l1,int r1,int i){
if(l1<=l[i]&&r1>=r[i])return maxx[i];
int mid=(l[i]+r[i])/2,xx,yy;
if(r1<=mid)return ask(l1,r1,i*2);
else if(l1>mid)return ask(l1,r1,i*2+1);
else{
xx=ask(l1,mid,2*i);
yy=ask(mid+1,r1,2*i+1);
return max(max(xx,yy),getleft(mid+1,r1,2*i+1)+getright(l1,mid,2*i));
}
}