求助
  • 板块学术版
  • 楼主lfxxx
  • 当前回复3
  • 已保存回复3
  • 发布时间2021/10/7 14:56
  • 上次更新2023/11/4 04:26:53
查看原帖
求助
520748
lfxxx楼主2021/10/7 14:56

写了一个二维线段树,但不知道求子树的编号,哪位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;
}
2021/10/7 14:56
加载中...