http://www.spoj.com/problems/GSS1/
题意：无更新询问区间最大连续和。
做法：线段树每个节点维护sum[rt],maxsum[rt],lsum[rt],rsum[rt]，分别区间和、区间最大和、区间左端最大和和区间右端最大和。
查询时按从左到右扫，维护ans为最大连续和，rans为到该段的右端最大连续和，扫到每一段时有：
ans = max(ans,maxsum[rt]);
ans = max(ans,rans+lsum[rt]);
rans = max(rsum[rt],rans+sum[rt]);
/*
*Author: Zhaofa Fang
*Created time: 2013-09-05-22.18 星期四
*/
#include <cstdio>
#include <cstdlib>
#include <sstream>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <string>
#include <utility>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std; typedef long long ll;
typedef pair<int,int> PII;
#define DEBUG(x) cout<< #x << ':' << x << endl
#define FOR(i,s,t) for(int i = (s);i <= (t);i++)
#define FORD(i,s,t) for(int i = (s);i >= (t);i--)
#define REP(i,n) for(int i=0;i<(n);i++)
#define REPD(i,n) for(int i=(n-1);i>=0;i--)
#define PII pair<int,int>
#define PB push_back
#define ft first
#define sd second
#define lowbit(x) (x&(-x))
#define INF (1<<30)
#define eps (1e-8) #define lson l , m , rt<<1
#define rson m + 1 , r , rt<<1|1
const int maxn = ;
int sum[maxn<<],maxsum[maxn<<],lsum[maxn<<],rsum[maxn<<];
int rans,ans;
void pushUp(int l,int r,int rt){
sum[rt] = sum[rt<<] + sum[rt<<|];
maxsum[rt] = max(maxsum[rt<<],maxsum[rt<<|]);
maxsum[rt] = max(maxsum[rt],rsum[rt<<]+lsum[rt<<|]);
lsum[rt] = max(lsum[rt<<],sum[rt<<]+lsum[rt<<|]);
rsum[rt] = max(rsum[rt<<|],sum[rt<<|]+rsum[rt<<]);
}
void build(int l,int r,int rt){
if(l == r){
scanf("%d",&sum[rt]);
lsum[rt] = rsum[rt] = maxsum[rt] = sum[rt];
return;
}
int m = (l + r) >> ;
build(lson);
build(rson);
pushUp(l,r,rt);
}
void query(int L,int R,int l,int r,int rt){
if(L <= l && r <= R){
ans = max(ans,maxsum[rt]);
ans = max(ans,rans+lsum[rt]);
rans = max(rsum[rt],rans+sum[rt]);
return;
}
int m = (l + r) >> ;
if(L <= m)query(L,R,lson);
if(m < R)query(L,R,rson);
}
int main(){
//freopen("in","r",stdin);
//freopen("out","w",stdout);
int n;
while(~scanf("%d",&n)){
build(,n,);
int Q;
scanf("%d",&Q);
while(Q--){
int l,r;
scanf("%d%d",&l,&r);
ans = rans = -INF;
query(l,r,,n,);
printf("%d\n",ans);
}
}
return ;
}
http://www.spoj.com/problems/GSS3/
题意：更新单点，询问区间最大连续和。
做法：做法与GSS1差不多，多了个修改。
/*
*Author: Zhaofa Fang
*Created time: 2013-09-13-12.56 星期五
*/
#include <cstdio>
#include <cstdlib>
#include <sstream>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <string>
#include <utility>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std; typedef long long ll;
typedef pair<int,int> PII;
#define DEBUG(x) cout<< #x << ':' << x << endl
#define FOR(i,s,t) for(int i = (s);i <= (t);i++)
#define FORD(i,s,t) for(int i = (s);i >= (t);i--)
#define REP(i,n) for(int i=0;i<(n);i++)
#define REPD(i,n) for(int i=(n-1);i>=0;i--)
#define PII pair<int,int>
#define PB push_back
#define ft first
#define sd second
#define lowbit(x) (x&(-x))
#define INF (1<<30)
#define eps (1e-8) #define lson l , m , rt<<1
#define rson m + 1 , r , rt<<1|1 const int maxn = ;
int sum[maxn<<],lsum[maxn<<],rsum[maxn<<],mx[maxn<<]; void pushUp(int rt){
sum[rt] = sum[rt<<] + sum[rt<<|];
mx[rt] = max(mx[rt<<],mx[rt<<|]);
mx[rt] = max(mx[rt],rsum[rt<<] + lsum[rt<<|]); lsum[rt] = max(lsum[rt<<],sum[rt<<] + lsum[rt<<|]);
rsum[rt] = max(rsum[rt<<|],sum[rt<<|]+rsum[rt<<]);
}
void build(int l,int r,int rt){
if(l == r){
scanf("%d",&sum[rt]);
mx[rt] = lsum[rt] = rsum[rt] = sum[rt];
return ;
}
int m = (l + r) >> ;
build(lson);
build(rson);
pushUp(rt);
}
void update(int k,int val,int l,int r,int rt){
if(l == k && k == r){
mx[rt] = lsum[rt] = rsum[rt] = sum[rt] = val;
return;
}
int m = (l + r) >> ;
if(k <= m)update(k,val,lson);
else update(k,val,rson);
pushUp(rt);
}
int ans,lans;
void query(int L,int R,int l,int r,int rt){
if(L <= l && r <= R){
ans = max(ans,mx[rt]);
ans = max(ans,lans+lsum[rt]);
lans = max(lans+sum[rt],rsum[rt]);
return;
}
int m = (l + r) >> ;
if(L <= m)query(L,R,lson);
if(m < R)query(L,R,rson);
}
int main(){
//freopen("in","r",stdin);
//freopen("out","w",stdout);
int n;
while(~scanf("%d",&n)){
build(,n,);
int Q;
scanf("%d",&Q);
while(Q--){
int op,x,y;
scanf("%d%d%d",&op,&x,&y);
if(!op)update(x,y,,n,);
else {
ans = lans = -INF;
query(x,y,,n,);
printf("%d\n",ans);
}
}
}
return ;
}