如何分析权值线段树上二分找一个数前驱的复杂度
  • 板块学术版
  • 楼主M1saka16I72
  • 当前回复8
  • 已保存回复8
  • 发布时间2024/9/7 11:16
  • 上次更新2024/9/7 14:55:15
查看原帖
如何分析权值线段树上二分找一个数前驱的复杂度
422684
M1saka16I72楼主2024/9/7 11:16

存不存在能使如下的代码一直往右侧节点递归但未能成功得到返回值,导致复杂度高于 log⁡v\log v 的情况?

int lst(int d,int l,int r,int p){
	if(!tr[p].v)	return 0;
	int mid = (l+r)>>1;
	if(tr[p<<1|1].v && mid+1<=d){
		int res = lst(d,mid+1,r,p<<1|1);
		if(res)	return res;
	}
	return lst(d,l,mid,p<<1);
}
2024/9/7 11:16
加载中...