关于区间查询有个疑问
查看原帖
关于区间查询有个疑问
600834
Skadiiiii楼主2024/10/23 13:27

这是100pts的区间查询

long long query(int id,int x,int y)
{
	if(x<=tr[id].l&&tr[id].r<=y)
		return tr[id].s;
	pushdown(id);
	int mid=(tr[id].l+tr[id].r)>>1;
	long long ans=0;
	if(x<=mid)ans+=query(id<<1,x,y);
	if(mid<y)ans+=query(id<<1|1,x,y);
	return ans;
}

这是10pts的区间查询

long long query(int id,int x,int y)
{
	if(x<=tr[id].l&&tr[id].r<=y)
		return tr[id].s;
	pushdown(id);
	int mid=(tr[id].l+tr[id].r)>>1;
	long long ans=0;
	if(x<=mid)ans+=query(id<<1,x,mid);
	if(mid<y)ans+=query(id<<1|1,mid+1,y);
	return ans;
}

可本蒟蒻觉得这两种query不是等价的吗?
查询id的左孩子时(x,y)和(x,mid)有什么区别?id的左孩子最右边不也只到mid吗? 求解答

2024/10/23 13:27
加载中...