我偏不信，用数组写了一个线段树，查询的时候定义了一个新的变量存合并后的节点，然后进行查询。 我感觉这个想法没什么问题呀。 然而。。。。。。。它wa了. 下面是我的代码

#include<cstdio>
#include<iostream> 
#define mid (l+r>>1)
#define N 500010
using namespace std;
int sum[N<<2],dat[N<<2],lmax[N<<2],rmax[N<<2],ans,n,m,a[N];
void up(int rt){
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
    dat[rt]=max(dat[rt<<1],max(dat[rt<<1|1],rmax[rt<<1]+lmax[rt<<1|1]));
    lmax[rt]=max(lmax[rt<<1],sum[rt<<1]+lmax[rt<<1|1]);
    rmax[rt]=max(rmax[rt<<1|1],sum[rt<<1|1]+rmax[rt<<1]);
}
void build(int rt,int l,int r){
    if(l==r){
        sum[rt]=dat[rt]=lmax[rt]=rmax[rt]=a[l];
        return;
    }
    build(rt<<1,l,mid);
    build(rt<<1|1,mid+1,r);
    up(rt);
    printf("rt:%d %d %d %d %d\n",rt,dat[rt],lmax[rt],rmax[rt],sum[rt]);
}
void change(int rt,int l,int r,int k,int val){
    if(l==r){
        sum[rt]=dat[rt]=lmax[rt]=rmax[rt]=val;
        return;
    }
    if(k<=mid) change(rt<<1,l,mid,k,val);
    else change(rt<<1|1,mid+1,r,k,val);
    up(rt);
}
int query(int rt,int l,int r,int L,int R){
    if(L<=l&&R>=r){
        return rt;
    }
    if(R<=mid) return query(rt<<1,l,mid,L,R);
    if(L>mid)return query(rt<<1|1,mid+1,r,L,R);
    int t1=query(rt<<1,l,mid,L,R),t2=query(rt<<1|1,mid+1,r,L,R);
    printf("t1:%d t2:%d",t1,t2);
    dat[ans]=max(dat[t1],max(dat[t2],rmax[t1]+lmax[t2]));
    lmax[ans]=max(lmax[t1],sum[t1]+lmax[t2]);
    rmax[ans]=max(rmax[t2],sum[t2]+rmax[t1]);
    sum[ans]=sum[t1]+sum[t2];
    printf("rt:%d %d %d %d %d\n",rt,dat[ans],lmax[ans],rmax[ans],sum[ans]); 
    return ans;
}
int main(){
    ans=N<<2-1;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    build(1,1,n);
    for(int i=1;i<=m;i++){
        int opt,x,y;
        scanf("%d%d%d",&opt,&x,&y);
        if(opt==1){
            if(x>y)swap(x,y);
            printf("%d\n",dat[query(1,1,n,x,y)]);
        }
        else
        change(1,1,n,x,y);
    }
}

用数组不能做是吗？