treap增加操作查询操作

//递归到叶子节点,一路维护信息即可
//查询排名

int query_rank(int k,int x){
	if (k==0) return 0;
	if (tr[k].v==x) return tr[tr[k].l].size+1;
	else if (x>tr[k].v)
	   return tr[tr[k].l].size+tr[k].w+query_rank(tr[k].r,x);
	else return query_rank(tr[k].l,x);
} 

//查询排名对应的个数

int query_num(int k,int x){
	if (k==0) return 0;
	if (x<=tr[tr[k].l].size)
	   return query_num(tr[k].l,x);
	else if (x>tr[tr[k].l].size+tr[k].w)
	  return query_num(tr[k].r,x-tr[tr[k].l].size-tr[k].w);
	else return tr[k].v;
} 
全部评论

相关推荐

07-10 12:17
已编辑
商丘师范学院 Java
后来123321:别着急,我学院本大二,投了1100份,两个面试,其中一个还是我去线下招聘会投的简历,有时候这东西也得看运气
无实习如何秋招上岸
点赞 评论 收藏
分享
05-14 20:34
门头沟学院 Java
窝补药贝八股:管他们,乱说,反正又不去,直接说680
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-08 17:10
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务