sicily 1800 序列，求长度在L-U之间的区间的最小值

   初学者，从很基础的开始写。
   我连二叉树都不是很熟悉就对这道题目感兴趣。适合初学者。
   首先是想到动归。
   参考别人的代码看到有二叉搜索树，上百科学习（有完整的讲解）。
   讲讲我的想法：
   1.当前区间的值=[i]+[i+1]...+[j]=sum[j]-sum[i];
   2.二元是比较麻烦的，故先固定一个，比如说j，然后寻到最大的sum[i]就是[1]-[j]之间的最小值。最短是L，所以接下来让j遍历L-n；
   3.怎么查找max(sum[i])就是搜索树的了。

建立的树序号： 

              1

        2          7

   4     5       6    8

区间:

           0-9

    0-4           5-9

0-2    3-4     5-7     8-9

tr[i]表示区间(a,b)中s[i]最大的。

#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdio>
using namespace std;
#define maxn 32777;
#define INF 1000000000

struct tree{int l,r,sum;};
 
tree tr[32777*4];
int n,L,U,s[32777];

void CreatTree(int m,int n,int x){
    tr[x].l=m; 
    tr[x].r=n;
    if(n==m) {tr[x].sum=s[m]; return;}

    int mid=(m+n)>>1;
    CreatTree(m, mid, x<<1);
    CreatTree(mid+1, n, (x<<1)+1);

    tr[x].sum=max(tr[x<<1].sum, tr[(x<<1)+1].sum);
}

int Search(int m,int n,int x){
    if(m==tr[x].l&&n==tr[x].r) return tr[x].sum;
    
    int mid = (tr[x].l+tr[x].r)>>1;
    
    if(n<=mid) return Search(m,n,(x<<1));
        else if(m>mid) return Search(m,n,(x<<1)+1);
            else return max(Search(m,mid,x<<1),Search(mid+1,n,(x<<1)+1));
} 

int main(){
    int n;
    while(scanf("%d",&n)==1&&n){
        scanf("%d%d",&L,&U);
        s[0]=0;
        for(int i=1;i<=n;++i){
            scanf("%d",&s[i]);
            s[i]+=s[i-1]; 
        }
        CreatTree(0,n,1);
        
/**********************************************************************/
//查看建立的树 
        cout<<endl;
        for(int i=1;i<=n;++i) cout<<s[i]<<" ";cout<<endl;
        for(int i=1;i<=n;++i) cout<<tr[i].sum<<" ";cout<<endl;
        for(int i=1;i<=n+n;++i) cout<<tr[i].l<<" ";cout<<endl;
        for(int i=1;i<=n+n;++i) cout<<tr[i].r<<" ";cout<<endl;
/**********************************************************************/ 
        
        int minn=INF;
        for(int i=L;i<=n;++i){
            int a=max(0,i-U);  // 0 1 ...L...U... (two cases at the condition of at least )
            int t=s[i]-Search(a,i-L,1); //以i为右端点
            if(t<minn) minn=t;
        }
        printf("%d
",minn);
    }
    
    return 0;
}