二维线段树找不出错误，查询时为负

二维线段树找不出错误 ，问题是求矩阵中各数字的和，运用四分法，若行相同了，则对列二分；若列相同了，则对行二分

#include <bits/stdc++.h>
#define maxn 1001
#define son1 rt<<2    //左上
#define son2 rt<<2|1  //左下
#define son3 rt<<2|2  //右上
#define son4 rt<<2|3  //右下
#define midl ((l+r)/2)
#define midh ((u+d)/2)
using namespace std;
int a[1001][1001];
struct node{
    int sum;
    int lazy;
};
node tree[(maxn<<2)*(maxn<<2)];
int mergetree(node a,node b,node c,node d){
    int res;
    res=a.sum+b.sum+c.sum+d.sum;
    return res;
}
void pushdown(int rt,int l,int r,int u,int d){
    if(tree[rt].lazy){
        if(l!=r&&u==d){
            tree[son1].lazy+=tree[rt].lazy;
            tree[son1].sum+=tree[rt].lazy*(midl-l+1);
            tree[son3].lazy+=tree[rt].lazy;
            tree[son3].sum+=tree[rt].lazy*(r-midl);
            return;
        }
        if(l==r&&u!=d){
            tree[son1].lazy+=tree[rt].lazy;
            tree[son1].sum+=tree[rt].lazy*(midh-u+1);
            tree[son2].lazy+=tree[rt].lazy;
            tree[son2].sum+=tree[rt].lazy*(d-midh);
            return;
        }
        tree[son1].lazy+=tree[rt].lazy;
        tree[son1].sum+=tree[rt].lazy*(midl-l+1)*(midh-u+1);
        tree[son3].lazy+=tree[rt].lazy;
        tree[son3].sum+=tree[rt].lazy*(r-midl)*(midh-u+1);
        tree[son4].lazy+=tree[rt].lazy;
        tree[son4].sum+=tree[rt].lazy*(r-midl)*(d-midh);
        tree[son2].lazy+=tree[rt].lazy;
        tree[son2].sum+=tree[rt].lazy*(d-midh)*(midl-l+1);
        tree[rt].lazy=0;
    }
  
}
void buildtree(int rt,int l,int r,int u,int d){
    tree[rt].lazy=0;
    if(l==r&&u==d){
        tree[rt].sum=a[l][u];
        return;
    }
    if(l!=r&&u==d){
        buildtree(son1,l,midl,u,u);
        buildtree(son3,midl+1,r,u,u);
        tree[son2].sum=tree[son4].sum=0;
        tree[son2].lazy=tree[son4].lazy=0;
        tree[rt].sum=mergetree(tree[son1],tree[son2],tree[son3],tree[son4]);
        return;
    }
    if(l==r&&u!=d){
        buildtree(son1,l,l,u,midh);
        buildtree(son2,l,l,midh+1,d);
        tree[son3].sum=tree[son4].sum=0;
        tree[son3].lazy=tree[son4].lazy=0;
        tree[rt].sum=mergetree(tree[son1],tree[son2],tree[son3],tree[son4]);
        return;
    }
    buildtree(son1,l,midl,u,midh); //左上
    buildtree(son2,l,midl,midh+1,d); //左下
    buildtree(son3,midl+1,r,u,midh);  //右上
    buildtree(son4,midl+1,r,midh+1,d);  //右下
    tree[rt].sum=mergetree(tree[son1],tree[son2],tree[son3],tree[son4]);
    return;
}
void update(int rt,int l,int r,int u,int d,int ql,int qr,int qu,int qd,int v){
    if(l<=ql&&qr<=r&&u<=qu&&qd<=d){
        tree[rt].sum+=v;
        tree[rt].lazy=v;
        return;
    }
    if(r<ql||l>qr||d<qu||u>qd){
        return;
    }
    pushdown(rt,l,r,u,d);
    if(l!=r&&u==d){
        update(son1,l,midl,u,u,ql,qr,qu,qd,v);
        update(son3,midl+1,r,u,u,ql,qr,qu,qd,v);
        tree[rt].sum=mergetree(tree[son1],tree[son2],tree[son3],tree[son4]);
        return;
    }
    if(l==r&&u!=d){
        update(son1,l,l,u,midh,ql,qr,qu,qd,v);
        update(son2,l,l,midh+1,d,ql,qr,qu,qd,v);
        tree[rt].sum=mergetree(tree[son1],tree[son2],tree[son3],tree[son4]);
        return;
    }
    
   update(son1,l,midl,u,midh,ql,qr,qu,qd,v); //左上
    update(son2,l,midl,midh+1,d,ql,qr,qu,qd,v); //左下
    update(son3,midl+1,r,u,midh,ql,qr,qu,qd,v);  //右上
   update(son4,midl+1,r,midh+1,d,ql,qr,qu,qd,v);  //右下
    tree[rt].sum=mergetree(tree[son1],tree[son2],tree[son3],tree[son4]);
    return;
}
int query(int rt,int l,int r,int u,int d,int ql,int qr,int qu,int qd){
    if(l<=ql&&qr<=r&&u<=qu&&qd<=d){
         
        return tree[rt].sum;
    }
    pushdown(rt,l,r,u,d);
    if(r<ql||l>qr||d<qu||u>qd){
        return 0;
    }
    if(l!=r&&u==d){
        return query(son1,l,midl,u,u,ql,qr,qu,qd)+query(son3,midl+1,r,u,u,ql,qr,qu,qd);
    }
    if(l==r&&u!=d){
        return  query(son1,l,l,u,midh,ql,qr,qu,qd)+ query(son2,l,l,midh+1,d,ql,qr,qu,qd);
    }
   
    return  query(son1,l,midl,u,midh,ql,qr,qu,qd)+query(son2,l,midl,midh+1,d,ql,qr,qu,qd)+query(son3,midl+1,r,u,midh,ql,qr,qu,qd)+  query(son4,midl+1,r,midh+1,d,ql,qr,qu,qd);
}

#include <bits/stdc++.h>
#define maxn 1001
#define son1 rt<<2 //左上
#define son2 rt<<2|1 //左下
#define son3 rt<<2|2 //右上
#define son4 rt<<2|3 //右下
using namespace std;
int a[1001][1001];
struct node{
long long sum;
int lazy;
};
node tree[(maxn<<2)(maxn<<2)];
long long mergetree(node a,node b,node c,node d){
long long res;
res=a.sum+b.sum+c.sum+d.sum;
return res;
}
void pushdown(int rt,int l,int r,int u,int d){
if(tree[rt].lazy){
int midl=(l+r)/2;
int midh=(u+d)/2;
if(l!=r&&u==d){
tree[son1].lazy+=tree[rt].lazy;
tree[son1].sum+=tree[rt].lazy(midl-l+1);
tree[son3].lazy+=tree[rt].lazy;
tree[son3].sum+=tree[rt].lazy*(r-midl);
tree[rt].lazy=0;
return;
}
if(l==r&&u!=d){
tree[son1].lazy+=tree[rt].lazy;
tree[son1].sum+=tree[rt].lazy*(midh-u+1);
tree[son2].lazy+=tree[rt].lazy;
tree[son2].sum+=tree[rt].lazy*(d-midh);
tree[rt].lazy=0;
return;
}
tree[son1].lazy+=tree[rt].lazy;
tree[son1].sum+=tree[rt].lazy*(midl-l+1)(midh-u+1);
tree[son3].lazy+=tree[rt].lazy;
tree[son3].sum+=tree[rt].lazy(r-midl)(midh-u+1);
tree[son4].lazy+=tree[rt].lazy;
tree[son4].sum+=tree[rt].lazy(r-midl)(d-midh);
tree[son2].lazy+=tree[rt].lazy;
tree[son2].sum+=tree[rt].lazy(d-midh)*(midl-l+1);
tree[rt].lazy=0;
}

}
void buildtree(int rt,int l,int r,int u,int d){
tree[rt].lazy=0;
if(l==r&&u==d){
tree[rt].sum=1;
return;
}
int midl=(l+r)/2;
int midh=(u+d)/2;
if(l!=r&&u==d){
buildtree(son1,l,midl,u,u);
buildtree(son3,midl+1,r,u,u);
tree[son2].sum=tree[son4].sum=0;
tree[son2].lazy=tree[son4].lazy=0;
tree[rt].sum=mergetree(tree[son1],tree[son2],tree[son3],tree[son4]);
return;
}
if(l==r&&u!=d){
buildtree(son1,l,l,u,midh);
buildtree(son2,l,l,midh+1,d);
tree[son3].sum=tree[son4].sum=0;
tree[son3].lazy=tree[son4].lazy=0;
tree[rt].sum=mergetree(tree[son1],tree[son2],tree[son3],tree[son4]);
return;
}
buildtree(son1,l,midl,u,midh); //左上
buildtree(son2,l,midl,midh+1,d); //左下
buildtree(son3,midl+1,r,u,midh); //右上
buildtree(son4,midl+1,r,midh+1,d); //右下
tree[rt].sum=mergetree(tree[son1],tree[son2],tree[son3],tree[son4]);
return;
}
void update(int rt,int l,int r,int u,int d,int ql,int qr,int qu,int qd,int v){
if(ql<=l&&r<=qr&&qu<=u&&d<=qd){
tree[rt].sum+=v;
tree[rt].lazy=v;
return;
}
if(r<ql||l>qr||d<qu||u>qd){
return;
}
pushdown(rt,l,r,u,d);
int midl=(l+r)/2;
int midh=(u+d)/2;
if(l!=r&&u==d){
update(son1,l,midl,u,u,ql,qr,qu,qd,v);
update(son3,midl+1,r,u,u,ql,qr,qu,qd,v);
} else if(l==r&&u!=d){
update(son1,l,l,u,midh,ql,qr,qu,qd,v);
update(son2,l,l,midh+1,d,ql,qr,qu,qd,v);
}else{
update(son1,l,midl,u,midh,ql,qr,qu,qd,v); //左上
update(son2,l,midl,midh+1,d,ql,qr,qu,qd,v); //左下
update(son3,midl+1,r,u,midh,ql,qr,qu,qd,v); //右上
update(son4,midl+1,r,midh+1,d,ql,qr,qu,qd,v); //右下
}
tree[rt].sum=mergetree(tree[son1],tree[son2],tree[son3],tree[son4]);
return;
}
long long query(int rt,int l,int r,int u,int d,int ql,int qr,int qu,int qd){
if(ql<=l&&r<=qr&&qu<=u&&d<=qd){
return tree[rt].sum;
}
if(r<ql||l>qr||d<qu||u>qd){
return 0;
}
pushdown(rt,l,r,u,d);
int midl=(l+r)/2;
int midh=(u+d)/2;
if(l!=r&&u==d){
return query(son1,l,midl,u,u,ql,qr,qu,qd)+query(son3,midl+1,r,u,u,ql,qr,qu,qd);
}
if(l==r&&u!=d){
return query(son1,l,l,u,midh,ql,qr,qu,qd)+ query(son2,l,l,midh+1,d,ql,qr,qu,qd);
}

return  query(son1,l,midl,u,midh,ql,qr,qu,qd)+query(son2,l,midl,midh+1,d,ql,qr,qu,qd)+query(son3,midl+1,r,u,midh,ql,qr,qu,qd)+  query(son4,midl+1,r,midh+1,d,ql,qr,qu,qd);

}

你好，我是有问必答小助手，非常抱歉，本次您提出的有问必答问题，技术专家团超时未为您做出解答


本次提问扣除的有问必答次数，将会以问答VIP体验卡（1次有问必答机会、商城购买实体图书享受95折优惠）的形式为您补发到账户。


因为有问必答VIP体验卡有效期仅有1天，您在需要使用的时候【私信】联系我，我会为您补发。