以下是两种线段树合并 merge 函数的写法:
int merge(int x,int y,int l,int r){
if (!x||!y)return x+y;
int mid=(l+r)>>1,now=++cnt;
tree[now].val=tree[x].val+tree[y].val;
tree[now].l=merge(tree[x].l,tree[y].l,l,mid);
tree[now].r=merge(tree[x].r,tree[y].r,mid+1,r);
return now;
}
int merge(int x,int y,int l,int r){
if (!x||!y)return x+y;
if (l==r){
tree[x].val+=tree[y].val;
return x;
}
int mid=(l+r)>>1;
tree[x].l=merge(tree[x].l,tree[y].l,l,mid);
tree[x].r=merge(tree[x].r,tree[y].r,mid+1,r);
tree[x].val+=tree[y].val;
return x;
}
蒟蒻求问,这两种写法有什么区别呢?