Ideia Noic 11 - Merge Sort Tree

noic-ideia11-ex1.cpp

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

const int maxn = 1e5+10;

int num[maxn];

// vector para cada nó da árvore
vector<int> tree[4*maxn];

void build(int node, int l, int r)
{
	if (l == r)
	{
		tree[node].push_back(num[l]);
		return;
	}

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

	build(2*node, l, mid); build(2*node+1, mid+1, r);

	int a = 2*node, b = 2*node+1;

	// a função merge() junta dois vectors em um só, deixando o vector final ordenado
	// para mais informações sobre esta funçao, confira a referência do C++
	merge(tree[a].begin(), tree[a].end(), tree[b].begin(), tree[b].end(), back_inserter(tree[node]));
}