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\n",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));

} 

}