题目链接：sicily 1136
解题思路： 要求区间内的最大子数组，而且访问可能很频繁，时间复杂度需要达到o(n*logn)，于是就很自然地想到了线段树。我们可以用线段树来保存区间的最大子数组，但是仔细想想又不对劲了，如果访问的区间跨越了两个小区间怎么破，所以，这并不只是一个简单的求区间连续和的问题，还要有点小技巧。 最大子数组怎么得到的，，还记得《算法导论》里面讲过一种用分治法来求最大子数组的方法吗（分治法之最大子数组）？ 假设我们要求区间[low , high]的最大子数组，并且已知[low , mid]和[mid+1 , high]的各种信息（mid为区间中点，这里的各种信息并未确定），我们要怎么得到最大子数组呢？于是有公式： root->max_sum=max( root->l->max_sum , root->r->max_sum , root->l->lmax+root->r->rmax ) 这里的lmax表示包含区间右边界的最大连续和，rmax则是包含左边界的最大连续和，由于题目最终需要求出区间，所以各种子数组的边界都需要记录，下面是线段树结构体的定义：
struct node{lmax,rmax;max_sum;//最大连续和int left_bound,right_bound;//最大连续和的左、右边界node *l,*r;node(int l,int r):left(l),right(r),l(NULL),r(NULL){}};
然后lmax和rmax也有公式： root->lmax=max( root->r->lmax , root->l->lmax+root->r->sum ) root->rmax=max( root->l->rmax , root->r->rmax+root->l->sum ) 最后还有一个细节，就是答案的区间[i , j]的 i , j 得最小，就没什么大问题了！
AC代码：
#include <bits/stdc++.h>using namespace std;int n,a[100005];struct node{int left,right,sum;long long lmax,rmax;int l_index,r_index;long long max_sum;int left_bound,right_bound;node *l,*r;node(int l,int r):left(l),right(r),l(NULL),r(NULL){}};void push_up(node* root){root->sum=root->l->sum+root->r->sum;root->lmax=root->r->lmax,root->l_index=root->r->l_index; //from mid to leftif(root->l->lmax+root->r->sum >= root->lmax){root->lmax=root->l->lmax+root->r->sum;root->l_index=root->l->l_index;}root->rmax=root->l->rmax,root->r_index=root->l->r_index; //from mid to rightif(root->r->rmax+root->l->sum > root->rmax){root->rmax=root->r->rmax+root->l->sum;root->r_index=root->r->r_index;}root->max_sum=root->l->max_sum;//max sumroot->left_bound=root->l->left_bound;root->right_bound=root->l->right_bound;if(root->l->lmax+root->r->rmax > root->max_sum){root->max_sum=root->l->lmax+root->r->rmax;root->left_bound=root->l->l_index;root->right_bound=root->r->r_index;}if(root->r->max_sum > root->max_sum){root->max_sum=root->r->max_sum;root->left_bound=root->r->left_bound;root->right_bound=root->r->right_bound;}}void create(node* root){int l=root->left,r=root->right;if(l<r){int mid=(l+r)>>1;root->l=new node(l,mid);root->r=new node(mid+1,r);create(root->l);create(root->r);push_up(root);}else{root->sum=a[l];root->lmax=root->rmax=root->sum;root->left_bound=root->right_bound=root->l_index=root->r_index=l;root->max_sum=root->sum;}}node query(node* root,int l,int r){if(root->left==l&&root->right==r)return *root;int mid=(root->left + root->right)/2;if(mid>=r)return query(root->l,l,r);else if(l>mid)return query(root->r,l,r);else{node ans_l=query(root->l,l,mid),ans_r=query(root->r,mid+1,r);node ans(l,r);ans.sum=ans_l.sum+ans_r.sum;ans.lmax=ans_r.lmax,ans.l_index=ans_r.l_index;//from mid to leftif(ans_l.lmax+ans_r.sum >= ans.lmax)ans.lmax=ans_l.lmax+ans_r.sum,ans.l_index=ans_l.l_index;ans.rmax=ans_l.rmax,ans.r_index=ans_l.r_index;//from mid to rightif(ans_r.rmax+ans_l.sum > ans.rmax)ans.rmax=ans_r.rmax+ans_l.sum,ans.r_index=ans_r.r_index;ans.max_sum=ans_l.max_sum,//max sumans.left_bound=ans_l.left_bound,ans.right_bound=ans_l.right_bound;if(ans_l.lmax+ans_r.rmax > ans.max_sum){ans.max_sum=ans_l.lmax+ans_r.rmax;ans.left_bound=ans_l.l_index,ans.right_bound=ans_r.r_index;}if(ans_r.max_sum > ans.max_sum)ans.max_sum=ans_r.max_sum,ans.left_bound=ans_r.left_bound,ans.right_bound=ans_r.right_bound;return ans;} }void print(node* root)//测试用{printf(“l:%d r:%d sum:%d\n”,root->left,root->right,root->sum);printf(“mid_to_left:%d :%d\n”,root->l_index,root->lmax);printf(“mid_to_right:%d :%d\n”,root->r_index,root->rmax);printf(“max: l:%d r:%d sum:%d\n\n”,root->left_bound,root->right_bound,root->max_sum);if(root->l)print(root->l);if(root->r)print(root->r);}int main(){int n,m;scanf(“%d %d”,&n,&m);for(int i=1;i<=n;i++)scanf(“%d”,&a[i]);node* root=new node(1,n);create(root);// print(root);int x,y;while(m–){scanf(“%d %d”,&x,&y);node tmp=query(root,x,y);printf(“%d %d %lld\n”,tmp.left_bound,tmp.right_bound,tmp.max_sum);}return 0;}
总结： 1、线段树真是个好东西，跟区间有关的查询，多考虑它； 2、分治法求最大子数组的方法也是挺重要的； 3、注重细节，千万不可手贱！！！
走过的路成为背后的风景，不能回头不能停留，若此刻停留，
