Informática - Ideia 11

Escrito por Lúcio Cardoso

Conhecimento prévio necessário:

Árvore de Segmentos (Segment Tree)

A Merge Sort Tree é uma extensão da Segment Tree, e por isso, é fortemente recomendado um bom entendimento desta estrutura antes de conferir esta Ideia.

Com a Merge Sort Tree, podemos responder diversos tipos de queries. Iremos demonstrar, em particular, a sua aplicação na seguinte query: Dado um vetor $V$ de tamanho $N$ ( $1 \leq N \leq 10^5$ ), indique quantos números maiores que $x$ existem em um segmento $[l, r]$ .

Descrição da Estrutura

A estrutura da Merge Sort Tree é bastante semelhante à da Segment Tree. No entanto, ao invés de guardarmos um valor inteiro no nó que representa o intervalo $[l, r]$ , guardaremos um vector ordenado de inteiros, contendo todos os números do intervalo $[l, r]$ de $V$ .

Perceba que, organizando a estrutura desta forma, em cada um dos $O(\log_{} N)$ níveis da Merge Sort Tree, a somatória do tamanho dos vectors utilizados será exatamente $N$ , pois contamos cada elemento de $V$ uma vez. Logo, a memória total da Merge Sort Tree é $O(N \log_{} N)$ .

Para construir a estrutura, usaremos uma função build semelhante à da Segment Tree. No entanto, sempre que chegarmos em uma folha, iremos inserir no seu vector o número no índice que esta representa. Após isso, para construir um nó que não é folha, juntaremos os nós filhos da esquerda e da direita usando o comando $merge()$ do C++, que junta dois vectors e os ordena em um só (com complexidade $O(N)$ ).

Segue o código da função build():

	// 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(2node, l, mid); build(2node+1, mid+1, r);

	int a = 2node, b = 2node+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]));
	}

view raw

noic-ideia11-ex1.cpp

hosted with ❤ by GitHub

Respondendo a query

Imagine que recebemos a mesma operação indicada no começo em um intervalo $[l, r]$ . Podemos visitar cada um dos $O(\log_{} N)$ nós da MS Tree que representam esse intervalo (da mesma maneira que a função query() da segment tree) e calcular a resposta de maneira independente para cada um deles.

Agora, reduzimos o problema para calcular a quantidade de elementos maiores que $x$ que existem em um vector ordenado (representando um nó da MS Tree). Podemos calcular isto usando a função upper_bound() do C++ em $O(\log_{} N)$ , pois esta função retorna um iterator para primeira posição com valor maior que $x$ no vector.

Desta maneira, a complexidade necessária para responder esta query é $O(\log_{}^2 N)$ , pois usamos uma operação em $O(\log_{} N)$ para $O(\log_{} N)$ nós.

Segue o código da função query():

	// 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(2node, l, mid, a, b, x)+query(2node+1, mid+1, r, a, b, x));
	}

view raw

noic-ideia11-ex2.cpp

hosted with ❤ by GitHub

Outras aplicações

Perceba que, para este problema em específico, usamos um vector em cada nó da nossa árvore, com memória $O(N \log_{} N)$ . Porém, para resolver outros tipos de problemas, podemos guardar outras estruturas nos nós da árvore, como por exemplo sets, maps, BITs ou até mesmo outra segment tree.

Contanto que o tamanho da estrutura dentro de um nó representando $[l, r]$ , seja $O(r-l+1)$ , podemos usá-la com complexidade de memória $O(N \log_{} N)$ . Logo, devemos tomar cuidado ao utilizar BITs ou segment trees dentro de um nó, pois estas não podem ter um tamanho fixo definido globalmente. Uma alternativa seria utilizar um vetor de vectors alocados dinamicamente para a BIT ou uma segment tree esparsa (utilizando ponteiros), por exemplo.