Fusão de Árvores de Segmentos

A complexidade espacial é determinada pelo número de operações ou pelo limite de espaço do problema, calculando-se o tamanho máximo do array.

Intuitivamente, a profundidade de uma árvore de segmentos é \(\lceil \log_2 n \rceil\), e definitivamente \(d = \lfloor \log_2 n \rfloor + 1\) é suficiente.

Para \(m\) operações (note que essas operações referem-se a modificações na árvore de segmentos, não necessariamente às consultas do problema), é necessário reservar espaço para \(O(md)\) nós.

Por exemplo, no problema modelo, o número de operações é \(4m\) (onde \(m\) é o número de modificações no enunciado).

Aqui está uma implementação alternativa:

int fundir(int esq, int dir, int u, int v) {
    if (u == 0 || v == 0) return u + v;
    int meio = (esq + dir) >> 1;
    if (esq == dir) {
        tr[u].max += tr[v].max;
        if (tr[u].max == 0) tr[u].id = 0;
        else tr[u].id = esq;
        return u;
    }
    tr[u].esq = fundir(esq, meio, tr[u].esq, tr[v].esq);
    tr[u].dir = fundir(meio + 1, dir, tr[u].dir, tr[v].dir);
    atualizar(u);
    return u;
}

Este método descarta as duas árvores de segmentos originais; após a fusão, apenas as informações de u são garantidas como corretas, e a estrutura de v pode ser comprometida.

Neste problema, consultamos apenas o valor da raiz. Por que o valor da raiz muda?

Logicamente, a raiz não deveria ser vinculada a outra raiz, então deveria permanecer correta.

Ao testar extensivamente, descobri que se \(u\) é o pai de \(v\) e \(u\) não foi modificado, então a raiz de u é nula. Após a fusão, a raiz de u se torna diretamente a raiz de v, alterando o valor do nó raiz (esta raiz passa a representar a árvore de segmentos de u, não a de v)...

Isso é uma armadilha sutil...

Exemplo de entrada:

7 3
1 2
2 3
2 4
4 5
1 6
6 7
5 6 1
6 1 5
1 3 4

Complexidade de tempo: cada operação de fusão percorre apenas os nós presentes em ambas u e v, além de seus filhos vinculados. O número de filhos vinculados é da mesma ordem que os próprios nós, então podemos considerar que removemos v. Portanto, a complexidade de cada fusão é proporcional ao número de nós removidos de v.

Como um nó é removido, deve ser visitado durante a fusão, e após a remoção, não será mais acessado. Assim, cada nó pode ser removido no máximo uma vez. O número total de nós é \(m \log n\), então a complexidade total é \(O(m \log n)\).

Divisão de Árvores de Segmentos

A divisão é similar ao FHQ Treap, podendo ser realizada por valor ou por tamanho.

A cada passo, analisamos os casos e atualizamos ambas as árvores.

Cada operação de divisão pode adicionar no máximo \(\log n\) novos nós. Inicialmente, existem \(4n\) nós, e no máximo \(n + m \log n\) nós. Diferente da análise de fusão, o número total de nós sempre cresce, mas independentemente do processo intermediário, o total de nós removidos não excede o número de nós inseridos. Portanto, o total de nós removidos é no máximo \(n + m \log n\), e outras operações são claramente \(m \log n\), resultando em uma complexidade total de \(O(m \log n)\).

O espaço necessário também é \(n + m \log n\).