Ideia Noic 11 - Merge Sort Tree

noic-ideia11-ex2.cpp

// Ideia Noic 11 - Merge Sort Tree
// Função query()

// calcula a quantidade de valores > x no intervalo [a, b] do vetor
int query(int node, int l, int r, int a, int b, int x)
{
	// estamos fora do intervalo
	if (l > b || r < a) return 0;

	// tree[node].end() aponta após a ultima posição do vector
	// logo, se subtrairmos deste ponteiro o primeiro iterador > x no vector, 
	// encontraremos a resposta para este nó
	if (l >= a && r <= b) 
		return tree[node].end()-upper_bound(tree[node].begin(), tree[node].end(), x);

	int mid = (l+r)>>1;

	// fazemos a recursão para os filhos do nó
	return (query(2*node, l, mid, a, b, x)+query(2*node+1, mid+1, r, a, b, x));
}