一个小问题
  • 板块学术版
  • 楼主JK_LOVER
  • 当前回复3
  • 已保存回复3
  • 发布时间2020/9/28 15:10
  • 上次更新2023/11/5 12:28:53
查看原帖
一个小问题
227824
JK_LOVER楼主2020/9/28 15:10

想问一下,线段树合并时,我是这样写的。

	int merge(int a,int b,int l,int r) {
		if(!a || !b) return a|b;
		int i = ++size;
		cnt[i] = cnt[a] + cnt[b];
		if(l == r) return i;int mid = l + r >> 1;
		lc[i] = merge(lc[a],lc[b],l,mid);
		rc[i] = merge(rc[a],rc[b],mid+1,r);
		return i;
	}

但是,如果这样写,是为什么出错,保证 cnt[0] = 0

	int merge(int a,int b,int l,int r) {
		// if(!a || !b) return a|b;
		int i = ++size;
		cnt[i] = cnt[a] + cnt[b];
		if(l == r || !a || !b) return i;int mid = l + r >> 1;
		lc[i] = merge(lc[a],lc[b],l,mid);
		rc[i] = merge(rc[a],rc[b],mid+1,r);
		return i;
	}
2020/9/28 15:10
加载中...