线段树合并时间复杂度为啥是 nlogn
  • 板块学术版
  • 楼主awdec
  • 当前回复11
  • 已保存回复11
  • 发布时间2024/7/29 23:15
  • 上次更新2024/7/30 09:29:34
查看原帖
线段树合并时间复杂度为啥是 nlogn
285856
awdec楼主2024/7/29 23:15
int merge(int k1,int k2,int l,int r){

	int mid=l+r>>1;

	if(!k1) return k2;

	if(!k2) return k1;

	if(l==r){

		tr[k1].maxn+=tr[k2].maxn;

		return k1;

	}

	ls(k1)=merge(ls(k1),ls(k2),l,mid);

	rs(k1)=merge(rs(k1),rs(k2),mid+1,r);

	push_up(k1);

	return k1;

}

有没有好一点的说明,洛谷板子题解区、oi-wiki 都没有找到较好的说明,大都是当成结论记。

2024/7/29 23:15
加载中...