busca_seg.cpp

int st[4*maxn]; //minha segtree de frequencia

int busca_seg(int p, int l, int r, int k)
{
	if(l == r) return l; //se l e r são iguais, cheguei no valor que eu queria

	int meio = (l+r)/2;

	if(st[p*2] >= k) //se meu filho da esquerda tiver pelo menos k valores, o k-esimo esta nele
	{
		return busca_seg(p*2, l, meio, k);
	}
	
	else //senao, o k-esimo esta no meu filho da direita 
	{
		return busca_seg(p*2+1, meio+1, r, k-st[p*2]);
	}
}