O^O刚学线段树合并,有个小小的细节问题
查看原帖
O^O刚学线段树合并,有个小小的细节问题
299810
issue_is_fw楼主2021/2/4 09:44

关于mergemerge函数递归到叶子节点时

l==rl==r

为什么不需要执行pos[x]=lpos[x]=l操作

这样不是漏掉了答案吗...

如果一开始pos[x]=0pos[x]=0pos[y]!=0pos[y]!=0

合并过来的话,pos[x]pos[x]就不是零了啊..

int merge(int x,int y,int l,int r)
{
	if( x==0||y==0 )	return x+y;
	if( l==r ){ sum[x]+=sum[y]; return x; }
	ls[x] = merge(ls[x],ls[y],l,mid);
	rs[x] = merge(rs[x],rs[y],mid+1,r);
	pushup(x,l,r);
	return x;
}
2021/2/4 09:44
加载中...