写了一个二维线段树,但不知道求子树的编号,哪位dalao教教我
#include<bits/stdc++.h>
#include<windows.h>
using namespace std;
struct s_tree{
int value;
int sign;
};
int one(int x)
{
return
}
int two(int x)
{
return
}
int three(int x)
{
return
}
int four(int x)
{
return
}
s_tree tree[10001];
int n,m;
int sum=0;
void bulid(int x,int x1=1,int y1=1,int x2=n,int y2=m)
{
//cout<<x1<<" "<<y1<<" "<<x2<<" "<<y2<<endl;
// Sleep(2000);
// sum++;
if(x2>n||y2>m||x1>x2||y1>y2)
{
return ;
}
if(x1==x2&&y1==y2)
{
cin>>tree[x].value;
return ;
}
int xmid=(x1+x2) >>1;
int ymid=(y1+y2) >>1;
bulid(one(x),xmid+1,y1,x2,ymid);
bulid(two(x),xmid+1,ymid+1,x2,y2);
bulid(three(x),x1,y1,xmid,ymid);
bulid(four(x),x1,ymid+1,xmid,y2);
tree[x].value=tree[one(x)].value+tree[two(x)].value+tree[three(x)].value+tree[four(x)].value;
}
void add(int x,int x1,int y1,int x2,int y2,int set,int X1=1,int Y1=1,int X2=n,int Y2=m)
{
// Sleep(2000);
if(X1==x1&&Y1==y1&&X2==x2&&Y2==y2)
{
tree[x].sign+=set;
tree[x].value+=set;
return ;
}
if(X1>=x1&&Y1>=y1&&X2<=x2&&Y2<=y2)
{
return ;
}
int xmid=(X1+X2)>>1;
int ymid=(Y1+Y2)>>1;
if(x2>xmid&&y1<=ymid)
{
add(one(x),y1,x2,y2,xmid+1,Y1,X2,ymid,set);
}
if(x2>xmid&&y2>ymid)
{
add(two(x),x1,y1,x2,y2,xmid+1,ymid+1,X2,Y2,set);
}
if(x1<=xmid&&y1<=ymid)
{
add(three(x),x1,y1,x2,y2,X1,Y1,xmid,ymid,set);
}
if(x1<=xmid&&y2>ymid)
{
add(four(x),x1,y1,x2,y2,X1,ymid+1,xmid,Y2,set);
}
tree[x].value=tree[one(x)].value+tree[two(x)].value+tree[three(x)].value+tree[four(x)].value;
}
void down(int x,int x1,int y1,int x2,int y2)
{
if(x1==x2&&y1==y2)
{
return ;
}
tree[one(x)].sign+=tree[x].sign;
tree[two(x)].sign+=tree[x].sign;
tree[three(x)].sign+=tree[x].sign;
tree[four(x)].sign+=tree[x].sign;
tree[one(x)].value+=tree[x].sign;
tree[two(x)].value+=tree[x].sign;
tree[three(x)].value+=tree[x].sign;
tree[four(x)].value+=tree[x].sign;
tree[x].sign=0;
return ;
}
int question(int x,int x1,int y1,int x2,int y2,int X1=1,int Y1=1,int X2=n,int Y2=m)
{
if(X1==x1&&Y1==y1&&X2==x2&&Y2==y2)
{
return tree[x].value;
}
if(X1>=x1&&Y1>=y1&&X2<=x2&&Y2<=y2)
{
return 0;
}
down(x,x1,y1,x2,y2);
int xmid=(X1+X2)>>1;
int ymid=(Y1+Y2)>>1;
int set=0;
if(x2>xmid&&y1<=ymid)
{
set+=question(one(x),x1,y1,x2,y2,xmid+1,Y1,X2,ymid);
}
if(x2>xmid&&y2>ymid)
{
set+=question(two(x),x1,y1,x2,y2,xmid+1,ymid+1,X2,Y2);
}
if(x1<=xmid&&y1<=ymid)
{
set+=question(three(x),x1,y1,x2,y2,X1,Y1,xmid,ymid);
}
if(x1<=xmid&&y2>ymid)
{
set+=question(four(x),x1,y1,x2,y2,X1,ymid+1,xmid,Y2);
}
return set;
}
int main()
{
cin>>n>>m;
bulid(1,1);
int k;
cin>>k;
for(int i=1;i<=k;i++)
{
int x1,y1,x2,y2,r;
scanf("%d",&x1);
scanf("%d",&y1);
scanf("%d",&x2);
scanf("%d",&y2);
scanf("%d",&r);
add(1,x1,y1,x2,y2,r);
}
int Q;
cin>>Q;
for(int i=1;i<=Q;i++)
{
int x1,y1,x2,y2;
scanf("%d",&x1);
scanf("%d",&y1);
scanf("%d",&x2);
scanf("%d",&y2);
cout<<question(1,x1,y1,x2,y2)<<endl;
}
return 0;
}