SPOJ GSS 1. Can you answer these queries I

제목
    n (1 < = n < = n < = 50000) 개의 정수 가 함 유 된 시퀀스 와 m 개의 query 를 주 십시오. 모든 query 의 형식 은 a b 입 니 다. 모든 query 에 대해 [a, b] 에서 가장 큰 연속 부분 과 출력 을 구 합 니 다.
방법 분석
    선분 트 리 로 구간 [L, R] 내의 유지 보수:
        Lmax: 왼쪽 a [L] 를 포함 한 최대 연속 과
        Rmax: 오른쪽 a [R} 을 포함 한 최대 연속 과
        sum: 전체 구간 의 모든 요소 의 합
        Max: 전체 구간 의 최대 연속 부분 과
    위로 전달 할 때:
        father.Lmax=max{Lson.Lmax, Lson.sum+Rson.Lmax}
        father.Rmax=max{Rson.Rmax, Rson,sum+Lson.Rmax}
        father.Max=max{Lson.Max, Rson.Max, Lson.Rmax+Rson.Lmax}
        father.sum=Lson.sum+Rson.sum
    이 문 제 를 풀 면서 새로운 선분 트 리 작성 법 을 배 웠 습 니 다. 구체 적 인 값 이 아 닌 노드 로 돌아 가 는 것 이 시간 효율 을 높이 고 코드 량 을 줄 였 습 니 다. 예전 에 쓴 200 줄 + 코드 는 너무 우아 하지 않 아서 70 줄 도 안 되 는 폭발 을 당 했 습 니 다!
참조 코드

#include 
#include 
#include 
#include 

using namespace std;

const int N=50010;
const int INT_INF=0x3fffffff;

int val[N];

class seg_tree
{
	private:

		struct data
		{
			int st, en, val, Max, Lmax, Rmax;
		} T[N<<2];

	public:

		data update(data Lson, data Rson)
		{
			data fa;
			fa.Lmax=max(Lson.Lmax, Lson.val+Rson.Lmax);
			fa.Rmax=max(Rson.Rmax, Rson.val+Lson.Rmax);
			fa.Max=max(max(Lson.Max, Rson.Max), Lson.Rmax+Rson.Lmax);
			fa.val=Lson.val+Rson.val;
			return fa;
		}

		void build(int id, int st, int en)
		{
			T[id].st=st, T[id].en=en;
			if(st==en)
			{
				T[id].val=T[id].Max=T[id].Lmax=T[id].Rmax=val[st];
				return;
			}
			int mid=(st+en)>>1;
			build(id<<1, st, mid), build(id<<1|1, mid+1, en);
			data now=update(T[id<<1], T[id<<1|1]);
			T[id].val=now.val, T[id].Max=now.Max, T[id].Lmax=now.Lmax, T[id].Rmax=now.Rmax;
		}

		data query(int id, int L, int R)
		{
			if(L<=T[id].st && T[id].en<=R)
			{
				return T[id];
			}
			int mid=(T[id].st+T[id].en)>>1;
			if(R<=mid) return query(id<<1, L, R);
			else if(L>mid) return query(id<<1|1, L, R);
			else return update(query(id<<1, L, mid), query(id<<1|1, mid+1, R));
		}
} seg;

int main()
{
	int n; scanf("%d", &n);
	for(int i=1; i<=n; i++)
		scanf("%d", &val[i]);
	seg.build(1, 1, n);
	int m; scanf("%d", &m);
	for(int i=1, L, R; i<=m; i++)
	{
		scanf("%d%d", &L, &R);
		printf("%d
", seg.query(1, L, R).Max);
	}
	return 0;
}