Escrito por Lúcio Cardoso
Conhecimento prévio necessário:
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():
https://gist.github.com/luciocf/88b0346b169c7906ab0a668db69cef7d
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():
https://gist.github.com/luciocf/92bcd510748355c69d55f19d8e39a03c
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.